一個有N個整數元素的一位數組（A[0]，A[1]，A[2]，...，A[n-1]），這個數組當然有很多子數組，那麼子數組之和的最大值是什麼？ 比如 -2 5 3 -6 4 -8 6 的最大子數組是 5 3。 法一： 挨個遍歷查找：
int maximum=-INF;
int sum;
for(int i=0;i<n;i++)
{
sum=0;
for(int j=i;j<n;j++)
{
sum+=A[j];
if(sum>maximum)
maximum=sum;
}
return maximum;
}
int maximum=-INF;
int sum;
for(int i=0;i<n;i++)
{
sum=0;
for(int j=i;j<n;j++)
{
sum+=A[j];
if(sum>maximum)
maximum=sum;
}
return maximum;
}
法二：
采用DP的方法，
int max(int x,int y)
{
return (x>y)?x:y;
}
int MaxSum(int*A,int n)
{
Start[n-1]=A[n-1];
All[n-1]=A[n-1];
for(i=n-2;i>=0;i--)
{
Start[n-1]=max(A[i],A[[i]+Start[i+1]);
All[i]=max(Start[i],All[i+1]);
}
return All[0];
}
int max(int x,int y)
{
return (x>y)?x:y;
}
int MaxSum(int*A,int n)
{
Start[n-1]=A[n-1];
All[n-1]=A[n-1];
for(i=n-2;i>=0;i--)
{
Start[n-1]=max(A[i],A[[i]+Start[i+1]);
All[i]=max(Start[i],All[i+1]);
}
return All[0];
}
