给一段数列，（有可能为负数），找出其中一段子数列，使得这段子数列中的所有元素和最大，如果所求的和为负数，请输出0
1.分治思想（时间复杂度为O(n*logn) )
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int max3(int a,int b,int c) { int mid; mid = max(a,b); return max(mid,c); } int sums(const int a[],int l,int r) { int maxlsum,maxrsum; int maxlbsum,maxrbsum; int lbsum,rbsum; if(l == r) if(a[l] > 0) return a[l]; else return 0; int mid = (l+r) >> 1; maxlsum = sums(a,l,mid); maxrsum = sums(a,mid+1,r); maxlbsum = 0,lbsum = 0; for(int i = mid;i >= l;i--) { lbsum += a[i]; if(lbsum > maxlbsum) maxlbsum = lbsum; } maxrbsum = 0,rbsum = 0; for(int i = mid+1;i <= r;i++) { rbsum += a[i]; if(rbsum > maxrbsum) maxrbsum = rbsum; } return max3(maxlsum,maxrsum,maxlbsum+maxrbsum); } int main() { int a[50]; int n; cin >> n; for(int i = 0;i < n;i++) cin >> a[i]; cout << sums(a,0,n-1) << endl; return 0; } 2.在线计算（时间复杂度为O(N) )
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int maxs(const int a[],int n) { int thissum = 0,maxsum = 0; for(int i = 0;i < n;i++) { thissum += a[i]; if(thissum > maxsum) maxsum = thissum; else if(thissum < 0) thissum = 0; } return maxsum; } int main() { int a[50]; int n; cin >> n; for(int i = 0;i < n;i++) cin >> a[i]; cout << maxs(a,n) << endl; return 0; }
