题解 | #连续子数组的最大和#

/**
 *
 * @param array int整型一维数组
 * @param arrayLen int array数组长度
 * @return int整型
 */
// 典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因
//为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变
//量max记录最大的dp值返回即可。


int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
    // write code here
    //int locate = FindfirstPositive(array, arrayLen);

    int temp = array[0], max = array[0];
    for (int i = 1; i < arrayLen; i++) {
        array[i] = array[i] + (array[i - 1] > 0 ? array[i - 1] : 0);
        if (array[i] > max) {
            max = array[i];
        }
    }

    return max;
}

难点在于子序列初始节点的更新条件

别人的非常巧妙的想法，能随着对数组的遍历，由之前的结果，实时更新子序列的节点位置。