yxCoding

I am a coder

一个不错的算法题

yxjoey posted @ 2008年3月29日 09:34 in C语言 with tags c 程序 , 2160 阅读

一个整数数组array, 在所有的子数组(从下标i到下标j)中最大的和,要求时间复杂度为O(n).
举个例子 int array[]={1, 4,  -5, 9, -2, -5, 4, 1}, 最大的子数组和为9(从0~3或者4~4)

  1. #include <stdio.h>
  2.  
  3. int subMax(int array[], int n){
  4.         int i;
  5.         int curMax=0;
  6.         int sum=0;
  7.         for(i=0; i<n; i++){
  8.                 if(array[i]<0)
  9.                         sum += array[i];
  10.                 else{
  11.                         int tmpMax = curMax;
  12.                         if(sum+array[i]>0)
  13.                                 curMax += sum+array[i];
  14.                         if(array[i]>curMax)
  15.                                 curMax = array[i];
  16.                         if(curMax == tmpMax)
  17.                                 sum += array[i];
  18.                         else
  19.                                 sum = 0;
  20.                 }
  21.         }
  22.         return curMax;
  23. }
  24.  
  25. int main(int argc, char *argv[]){
  26.         int array[]={1, 4-5, 9, -2, -5, 4, 1};
  27.         printf("%d \n", subMax(array, sizeof(array)/sizeof(array[0])));
  28. }

最初的想法就是用几个循环算出所有的子和,然后找最大的。但是这个算法太没有效率了。
从分析角度来看

  • 1. 最大子和串的首尾肯定都是正数
  • 2. 从左向右看,在当前最大子和串的基础上,是否要包含下一个正数,我们必须看下一个正数的大小是否可以抵消先前的负数值
  • 3. 有可能当前的单个字符的值就已经比前面的子串和大了,甚至比用规则2算出的值更大

附:

今天又开始复习一些算法方面的小题目,偶然有遇到这道题,也看到了一个解法
这个解法代码简单很多,而且容易理解

  1. int max_sub2(int a[], int size)
  2. {
  3.         int i,max=0,temp_sum=0;
  4.         for(i=0;i<size;i++)
  5.         {
  6.                 temp_sum+=a[i];
  7.                 if(temp_sum>max)
  8.                         max=temp_sum;
  9.                 else if(temp_sum<0)
  10.                         temp_sum=0;
  11.         }
  12.         return max;
  13. }

Avatar_small
匡匡 说:
2008年9月10日 00:30

你把下面那个程序你用一组数组里面全部是负数试试结果看看....这样明显考虑问题不全.

Avatar_small
匡匡 说:
2008年9月10日 00:30

欢迎跟我联系,也是算法爱好者.
kcuiyun@126.com

Head_small
yxjoey 说:
2008年9月10日 06:32

我测试过的,结果是0,也就是不取任何数,应该也算是对的吧~


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter