题意：给定n个整数（可能为负整数）组成的序列a1，a2.......an,求该序列子段和的最大值（子段必须连续）,当所有整数为负整数定义其最大子段之和为0.
方法一：暴力 O(n^2)
#include<iostream>
#include<vector>
using namespace std;
int pd(int arr[], int n,int &best_i,int &best_j)
{
int sum, tmp;
sum = 0;
tmp = 0;
for (int i = 1; i <= n; i++)
{
tmp = 0;
for (int j = i; j <= n; j++)
{
tmp += arr[j];
if (tmp > sum)
{
sum = tmp;
best_i = i;
best_j = j;
}
}
}
return sum;
}
int main()
{
int arr[] = {0, -2,11,-4,13,-5,-2 };
int n = sizeof(arr) / sizeof(int);
int best_i, best_j;
best_i = 0;
best_j = 0;
cout << "max_value:" << pd(arr, n, best_i, best_j) << endl;
cout<<" best_i:" << best_i << " best_j: " << best_j << endl;
return 0;
}
分治法：
#include<iostream>
#include<vector>
using namespace std;
int pd(int arr[], int left, int right)
{
if (left == right)
{
if (arr[left] >= 0)
return arr[left];
else
return 0;
}
int center = (left + right) / 2;
int leftsum = pd(arr, left, center);
int rightsum = pd(arr, center + 1, right);
int s1,s2,lefts,rights,sum;
s1 = 0;
lefts = 0;
sum = 0;
for (int i = center; i >= left; i--)
{
lefts += arr[i];
if (lefts > s1)
s1 = lefts;
}
s2 = 0;
rights = 0;
for (int i = center+1; i <= right; i++)
{
rights += arr[i];
if (rights > s2)
s2 = rights;
}
sum = s1 + s2;
if (sum < leftsum)
sum = leftsum;
if (sum < rightsum)
sum = rightsum;
return sum;
}
int main()
{
int arr[] = { 0, -2,11,-4,13,-5,-2 };
int n = sizeof(arr) / sizeof(int);
cout << "Max_value: " << pd(arr, 1, n);
return 0;
}
dp:
#include<iostream>
#include<vector>
using namespace std;
int dp(int arr[], int n)
{
int* dp = new int[n + 1];
dp[1] = arr[1];
int cnt = 0;
int max_sum;
max_sum = 0;
for (int i = 2; i <= n; i++)
{
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
if (arr[i] < 0)
cnt++;
if (dp[i]>max_sum)
max_sum = dp[i];
}
if (cnt == n)
return 0;
return max_sum;
}
int main()
{
int arr[] = { 0, -2,11,-4,13,-5,-2 };
int n = sizeof(arr) / sizeof(int);
//cout << "Max_value: " << pd(arr, 1, n);
cout << "Max_value: " << dp(arr, n);
return 0;
}
