解法思路:在一段数组中,以每个数组下标为末尾的最大连续子数组,判断前一个连续数组和是否大于0,大于就可以加上该数构成一个更大的连续子数组;否则,自己组成一个连续数组。最后,遍历整个数组找出最大值。
#include<iostream> #include<cstdio> using namespace std; const int N=100000; int main() { int i,j,k; int a[N]; int sum[N]; int n; printf("请输入数组个数:\n"); cin>>n; for(i=1;i<=n;i++) cin>>a[i]; sum[1]=a[1]; int maxn=sum[1]; for(i=2;i<=n;i++) { if(sum[i-1]>0) sum[i]=a[i]+sum[i-1]; else sum[i]=a[i]; maxn=max(maxn,sum[i]); } cout<<maxn<<endl; return 0; }