求一维数组的最大子数组,程序有点不明白,麻烦大虾帮忙说明下
给定一个长度为n的一维数组a,请找出此数组的一个子数组,使得此子数组的 和sum=a[i]+a[i+1]+……+a[j]最大,其中i>=0,i<n,j>=i,j<n,
例如 31 -41 59 26 -53 58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。
网上直接穷举法的程序如下,麻烦说明下标红色的作用
//直接穷举法,求出所有可能的组合和 O(N^3)
int getSum1(int a[],int N)
{
int max=-10000000;
for(int i=0;i<N;i++)
{
for(int j=i;j<N;j++)
{
int tmp=0;
for(int k=i;k<=j;k++)
tmp+=a[k];
if(tmp>max)
max=tmp;
}
}
return max;
}
下边是我所想的解法,麻烦帮忙看下行不行(简单验证是OK,不过不清楚是否有BUG)
int getSum1(int a[],int N)
{
int max=-10000000;
int tmp=0;
for(int i=0;i<N;i++)
{
tmp=0;
for(int j=i;j<N;j++)
{
tmp+=a[j];
if(tmp>max)
max=tmp;
}
}
return max;
}