LeetCode/普通数组/1. 最大子数组和.md

最大子数组和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2：

输入：nums = [1] 输出：1 示例 3：

输入：nums = [5,4,-1,7,8] 输出：23

提示：

1 <= nums.length <= 105 -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路

• 前缀和
  • prefix
  • prefix[0] = 0
  • prefix[n]: [0, n)
  • n <= nums.length
• 遍历
  • 维护更新最小 prefix （初始为 0）
  • 当前数减去此前 prefix获取答案，如果答案变大，则更新 (初始化为 Integer.MIN_VALUE)

代码

class Solution {
    public int maxSubArray(int[] nums) {
        // Special
        if (nums == null || nums.length == 0) return 0;
        // Init
        int len = nums.length;
        int[] prefix = new int[len + 1];
        prefix[0] = 0;
        // Cal: Prefix Sum
        for (int i = 0; i < len; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        // Ans
        int minPrefix = prefix[0];
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= len; i++) {
            ans = Math.max(ans, prefix[i] - minPrefix);
            minPrefix = Math.min(minPrefix, prefix[i]);
        }

        return ans;
    }
}