C++ 数组求和

C++ 数组求和

//题目描述：
//输入一个整形数组，数组里有正数也有负数。
//数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
//求所有子数组的和的最大值。要求时间复杂度为O(n)。

#include <iostream>   
using namespace std;
  
//int maxSum(int* a, int n)   
//{   
//    int sum=0;   
//    //其实要处理全是负数的情况，很简单，如稍后下面第3点所见，直接把这句改成："int sum=a[0]"即可   
//    //也可以不改，当全是负数的情况，直接返回0，也不见得不行。   
//    int b=0;   
//       
//    for(int i=0; i<n; i++)   
//    {   
//        if(b<0)           //...   
//            b=a[i];   
//        else  
//            b+=a[i];   
//        if(sum<b)   
//            sum=b;   
//    }   
//    return sum;   
//}   
//  
int main()   
{   
	const int size = 13;
    int a[size]={1, -2, 3, 10, -4, -70000, 2, -5,7,8,9,-10,-2};  
    int *sum = new int [size];
	int result = 0;
    //int a[]={-1,-2,-3,-4};  //测试全是负数的用例   
  //  cout<<maxSum(a,8)<<endl;
	sum[0] = a[0];
	for(int i = 0; i< size; i++)
	{
	  result = max(result, sum[i]);
      sum[i+1] = max(a[i+1], sum[i] + a[i+1]);
    
	}
	cout << result << endl;
	for(int i = 0;i < size; i++)
	{
	 cout <<"sum= " << sum[i] << endl;
	}
    return 0;   
}   
//如果a[i]和前面的sum之和大于a[i]，则a[i]作为老数组的元素。
//如果a[i]和前面的sum之和小于a[i] 则a[i]作为新数组的第一个元素。