[剑指 Offer 第 2 版第 42 题] “连续子数组的最大和”做题记录

第 42 题：连续子数组的最大和

传送门：连续子数组的最大和，牛客网 online judge 地址。

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

样例：

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

同 LeetCode 第 53 题，题解传送门：LeetCode 第 53 题：连续子数组的最大和。

“大雪菜”的做法：状态：以前一个数结尾的“连续子数组的最大和”为状态。

C++ 代码：

分析：

• 根据“最长公共子序列”问题的思路，我们在考虑数组的时候，定义以当前数组元素为结尾的连续子数组，往往会使用情况变得简单一些。
• 设置状态：dp[i] 以 i 结尾的子数组的最大和。
• 考虑状态转移方程：

如果 nums[i] < 0，dp[i] = max(dp[i-1] + nums[i],nums[i]); 如果 nums[i] >= 0，dp[i] = dp[i-1] + nums[i];

综上所述，不论当前考虑的数组元素是大于等于 0 还是小于 0，只要满足 dp[i] = max(dp[i-1] + nums[i], nums[i]) 就可以了，这就是状态转移方程。

Java 代码：

  public class Solution {

        public int FindGreatestSumOfSubArray(int[] array) {
            int n = array.length;
            if (n == 0) {
                return 0;
            }
            int[] dp = new int[n];
            dp[0] = array[0];
            int res = array[0];
            for (int i = 1; i < n; i++) {
                dp[i] = Integer.max(dp[i - 1] + array[i], array[i]);
                res = Integer.max(res, dp[i]);
            }
            return res;
        }

        public static void main(String[] args) {
            int[] nums = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
            Solution solution = new Solution();
            int findGreatestSumOfSubArray = solution.FindGreatestSumOfSubArray(nums);
            System.out.println(findGreatestSumOfSubArray);
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/