最大子段和【模板】

直接上模板：

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;
}