给定一个数组，求它的一个子数组，使其求和最大。
这个问题的应用：给定一只股票很多天的价格，计算从哪天买进哪天卖出能获得最大利润。
给定
prices：100 113 98 87 65 78 120 110 115
计算delta
delta： 13 -15 -11 -22 13 42 -10 5
求delta数组的最大连续子数组就能得到最大利润。
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1231
解法1：Devide and Conquer
1）将delta按中点分为两个数组left[l...mid]、right[mid+1...r]，最大子数组要么在left中，要么在right中，要么跨越left和right。
2）将其递归划分至原子问题，left中一个元素，right中一个元素。最大子数组要么是left[l]，要么是right[r]，要么是left[l]+right[r]。
3）先不考虑跨越left和right的情况，那么求left和right中的最大子数组，就是原问题的子问题，原问题时间复杂度T(n)，该子问题复杂度为T(n/2)。
4）将求跨越left和right的最大子数组的问题额外处理。其最大值一定是 left中以mid为右端点的最大子数组 加上 right中以mid+1为左端点的最大子数组。求这个问题的时间复杂度可以做到O(n)。最终T(n)=2T(n/2)+O(n)，整个问题的复杂度为O(nlogn)。
#include<iostream> #include<cstdio> using namespace std; #define N 10005 struct Pair { int sum, left,right; Pair() {} explicit Pair(int s, int l, int r) { sum = s; left = l; right = r; } bool operator < (const Pair& p)const { return sum < p.sum; } bool operator <= (const Pair& p)const { return sum <= p.sum; } }; int n, num[N],preSum[N],sufSum[N]; Pair findMaxCrossSubarr(int l, int r) { int mid = (l + r) / 2,lmax_l=mid,rmax_r=mid+1,lmax=num[mid],rmax=num[mid+1]; for (int i = l; i < mid; i++) { int tmp = preSum[mid] - preSum[i - 1]; if (tmp > lmax) { lmax = tmp; lmax_l = i; } } for (int i = mid + 2; i <= r; i++) { int tmp = sufSum[mid + 1] - sufSum[i+1]; if (tmp > rmax) { rmax = tmp; rmax_r = i; } } //cout << rmax + lmax << " " << lmax_l << " " << rmax_r << endl; /*if(rmax+lmax<0) return Pair(0, l, r); else */ return Pair(rmax + lmax, lmax_l, rmax_r); } Pair findMaxSubarr(int l, int r) { if (l == r) return Pair(num[l], l, r); int mid = (l + r) / 2; Pair lpair = findMaxSubarr(l, mid); Pair rpair = findMaxSubarr(mid + 1, r); Pair xpair = findMaxCrossSubarr(l, r); //cout << "*" << lpair.sum << " " << rpair.sum << " " << xpair.sum << endl; if (rpair <= lpair&&xpair <= lpair) return lpair; else if (lpair < rpair&&xpair < rpair) return rpair; else return xpair; } int main() { while (scanf_s("%d", &n) != EOF && n) { for (int i = 1; i <= n; i++) { scanf_s("%d", &num[i]); preSum[i] = preSum[i - 1] + num[i]; } for (int i = n; i > 0; i--) sufSum[i] = sufSum[i + 1] + num[i]; Pair res = findMaxSubarr(1, n); //printf("%d %d %d ", res.sum, res.left, res.right); if (res.sum < 0) printf("0 %d %d ", num[1], num[n]); else printf("%d %d %d ", res.sum, num[res.left], num[res.right]); //cout << endl; } return 0; }
解法2：Dynamic Programming 线性时间复杂度
假如知道以r为右端点的最大子数组，将其扩展到以r+1为右端点的最大子数组，若dp[r]>=0，则dp[r+1]=dp[r]+num[r+1]；若dp[r]<0，则dp[r+1]=num[r+1]；
#include<iostream> #include<cstdio> using namespace std; #define N 10005 int main() { int n; while (scanf_s("%d", &n) != EOF && n) { int num[N]; for (int i = 1; i <= n; i++) scanf_s("%d", &num[i]); int dp = -1, dp1 = 0, l = 0, r = 0, maxn = -1, tl = 0, tr = 0; for (int i = 1; i <= n; i++) { if (dp < 0) { dp = num[i]; tl = tr = i; } else { dp += num[i]; tr = i; } if (dp > maxn) { maxn = dp; l = tl; r = tr; } } if(maxn<0) printf("0 %d %d ", num[1], num[n]); else printf("%d %d %d ", maxn, num[l], num[r]); } return 0; }