直接上模板:
int MaxSub (int a[],int N)//此为只需要求最大的和,时间复杂度是O(n)
{
int *dp = new int(N);
int max, i;
max = dp[0] = a[0];
for (i=1; i<N; i++)
{
if (dp[i-1] > 0)
dp[i] = dp[i-1] + a[i];
else
dp[i] = a[i];
if (dp[i] > max)
max = dp[i];
}
delete dp;
return max;
}