PAT 解题报告 1007. Maximum Subsequence Sum (25)

Overview

PAT 解题报告 1007. Maximum Subsequence Sum: 保存一个最大字段和以及一个当前子段和, 如果当前字段和大于当前最大字段和, 那么更新这个最大字段和, 如果当前字段和为负数的时候, 直接把当前字段和甚设置成0

PAT 解题报告 1007. Maximum Subsequence Sum (25)

求最大连续子段和并且输出该最大字段和序列的第一个和最后一个元素

算法分析:

经典DP问题, 基于这样一个事实:保存一个最大字段和以及一个当前子段和, 如果当前字段和大于当前最大字段和, 那么更新这个最大字段和, 如果当前字段和为负数的时候, 直接把当前字段和甚设置成0, 求最大字段和算法如下:

int MaxSum(int A[], int N) {
    int currentSum = 0;
    int maxSum = 0;
    for(int i = 0; i < N; ++i) {
        currentSum += A[i];
        if(currentSum > maxSum) maxSum = currentSum;
        else if(currentSum < 0) currentSum = 0;
    }
    return maxSum;
}

由于这个题目里面还需要保存最大子段和的第一个和第二个元素, 加一些额外的变量记录以及在对应的更新maxSum和把currentSum设置成0的时候对应进行维护就行了. 算法复杂度O(N)

注意点:

当序列中有0但是其他都是负数的时候, 不是输出真个序列的第一个和最后一个元素,而是输出第一个0. 比如3 -1 0 -1 应当输出 0 0 0

Summary

PAT 解题报告 1007. Maximum Subsequence Sum: 保存一个最大字段和以及一个当前子段和, 如果当前字段和大于当前最大字段和, 那么更新这个最大字段和, 如果当前字段和为负数的时候, 直接把当前字段和甚设置成0

Written on April 11, 2013