看到这个题目，我首先想到就是暴力解决
求出所有的子数组的和，取出最大值即可
但其中是可以有优化的
如 子数组【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.csdn.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;
}
这方法很不错，我就转过来了。