题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
分析:
分析:O(n)的复杂度,也就是要求过一遍这个数组就要执行结束,要求最大的子数组,那么此子数组的开始大于0的值,向后读取,如果计算得到负值,那么前面的结果就不值得保留,从新从最新的地方加起。如果最后一个数是负值,那么最后一个值不需要,所以需要另一个参数来保留当前最大值。
当然,如果这个数组全部是小于等于0,那么最大的值是绝对值最小的一个数,我们可以用一个数来保存
solution
<pre><code>
include "stdio.h"
include "stdlib.h"
include "math.h"
//找到字数组的最大和
int find(int a ,int len){
int sum=0;
int b=0;//保留临时结果
int i=0;
//保留最小的绝对值,全负数组用
int c=abs(a);
for(;i<len;i++){
if (abs(*(a+i))<c)
c=abs(*(a+i));
if(b<0){
b=*(a+i);
}else{
b+=*(a+i);
}
if (*(a+i)>0){
sum=b;
}
}
if (sum!=0)
return sum;
else
return -c;
}
int main(){
int a[10]={1, -2, 3, 10, -4, 7, 2, -5};
int b[10]={-10,-2,-3,-5,-9,-10,-18,-7};
int c[10]={-10,-2,0,-5,-9,-10,-18,-7};
printf ("a的子数组最大和是%d\n",find(a,8));
printf ("b的子数组最大和是%d\n",find(b,8));
printf ("c的子数组最大和是%d\n",find(c,8));
return 0;
}
</code></pre>
执行结果:
<pre><code>
a的子数组最大和是18
b的子数组最大和是-2
c的子数组最大和是0
</code></pre>
网友评论
for(;i<0){
b=*(a+i);
}else{
b+=*(a+i);
}
if (*(a+i)>0){
sum=b;
}
}