homework-01 "最大子数组之和"的解决过程

看到这个题目，我首先想到就是暴力解决

求出所有的子数组的和，取出最大值即可

但其中是可以有优化的

如 子数组【3:6】可以用【3:5】+【6】来计算

即可以将前面的计算结果保留下来，减少后面的重复计算

我是用C++实现的

代码如下

 #include <iostream>

 /*
 求出所有字串和，取最大值
 其中sun为用来存放结果的数组
 后面的字串和可由前面的字串和再加一个数得到
 可以减少运算次数
 */
 int maxSum0(int* a,int n){
     int sum[][];
     int max = ;
     for(int i=; i<n; i++){
         sum[][i] = a[i];
         std::cout<<a[i]<<" ";
         if(max < a[i])
             max = a[i];
     }
     std::cout<<std::endl;

     for(int i=; i<n; i++){
         for(int j=i;j<n;j++){
             sum[i][j] = sum[i-][j-]+sum[][j];
             std::cout<<sum[i][j]<<" ";
             if(max < sum[i][j])
                 max = sum[i][j];
         }
         std::cout<<"\n";
     }
     return max;
 }

 int main(){
     int a[]={, -, , , -, , , -, -};
     std::cout<<maxSum0(a,)<<std::endl;
     return ;
 }

测试结果

我把所有子数组和都打印出来了，结果是正确的

分析

我的算法时间复杂度应该是O(n^2),因为在做子数组求和运算过程中，每一个子数组求和都只需要做一次加法运算就可得到，子数组一共为n*(n+1)/2个

所以时间复杂度为O(n^2)

网上别人的好方法

这是我在http://blog.****.net/v_JULY_v/article/details/6444021上看到的

时间复杂度读仅为O(n)

 /*
 我看着这代码总觉的写的太简单了、、、
 可是测试结果都没错。。

 每一次累加到小于零的子串和时就从新开始
 */
 int maxSum1(int* a, int n){
     int max=;
     int b=;
     for(int i=; i<n; i++)
     {
         if(b<)
             b=a[i];
         else
             b+=a[i];
         if(max<b)
             max=b;
     }
     return max;
 }

这方法很不错，我就转过来了。