一个不错的算法题
一个整数数组array, 在所有的子数组(从下标i到下标j)中最大的和，要求时间复杂度为O(n).
举个例子 int array[]={1, 4, -5, 9, -2, -5, 4, 1}, 最大的子数组和为9（从0～3或者4～4）
-
#include <stdio.h>
-
-
int subMax(int array[], int n){
-
int i;
-
int curMax=0;
-
int sum=0;
-
for(i=0; i<n; i++){
-
if(array[i]<0)
-
sum += array[i];
-
else{
-
int tmpMax = curMax;
-
if(sum+array[i]>0)
-
curMax += sum+array[i];
-
if(array[i]>curMax)
-
curMax = array[i];
-
if(curMax == tmpMax)
-
sum += array[i];
-
else
-
sum = 0;
-
}
-
}
-
return curMax;
-
}
-
-
int main(int argc, char *argv[]){
-
int array[]={1, 4, -5, 9, -2, -5, 4, 1};
-
}
最初的想法就是用几个循环算出所有的子和，然后找最大的。但是这个算法太没有效率了。
从分析角度来看
- 1. 最大子和串的首尾肯定都是正数
- 2. 从左向右看，在当前最大子和串的基础上，是否要包含下一个正数，我们必须看下一个正数的大小是否可以抵消先前的负数值
- 3. 有可能当前的单个字符的值就已经比前面的子串和大了，甚至比用规则2算出的值更大
附：
今天又开始复习一些算法方面的小题目，偶然有遇到这道题，也看到了一个解法
这个解法代码简单很多，而且容易理解
-
int max_sub2(int a[], int size)
-
{
-
int i,max=0,temp_sum=0;
-
for(i=0;i<size;i++)
-
{
-
temp_sum+=a[i];
-
if(temp_sum>max)
-
max=temp_sum;
-
else if(temp_sum<0)
-
temp_sum=0;
-
}
-
return max;
-
}
yxjoey
最新评论
最新留言
友情链接
我的豆瓣收藏
浏览计数器
62379
2008年9月10日 00:30
你把下面那个程序你用一组数组里面全部是负数试试结果看看....这样明显考虑问题不全.
2008年9月10日 00:30
欢迎跟我联系,也是算法爱好者.
kcuiyun@126.com
2008年9月10日 06:32
我测试过的，结果是0，也就是不取任何数，应该也算是对的吧～