最大子数组和

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

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

示例 ：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

题解：

最简单的思路还是从暴力枚举开始, 枚举所有子数组并求和, 当然时间复杂度肯定为 n^2 以上

有一些算法经验的小伙伴这时候会想到将解决方案往 双指针 上靠, 下面我们就来简单说明一下这种方法的可行性：首先答案是否定的, 我们在移动指针时都有明确的条件来判断什么时候移动左指针和右指针, 而在本题中我们无法得到指针移动的条件。本题中我们要跟踪当前子数组的最大和, 这是一个动态变化的状态(会增会减)双指针只能在某种情况下有效，但在需要动态更新的情况下，它可能会变得繁琐且不高效。

下面我们来介绍本题的解法

解法一: 前缀和

对于一个子数组 [-3,2,-1,5,...], 我们取的时候一定是不会取-3的,而是从2开始(加上-3一定小)

同理, 我们定义一个概念: 前缀和(代表数组中某个值nums[i]的前面所有值的和), 如果nums[i]的前缀和小于0, 那我们就要丢弃nums[i]的前缀和, 并从当前位置重新记录前缀和。

public class maxSumSubArray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(getMaxSubArraySumByPrefix(nums));
    }
    
    public static int getMaxSubArraySumByPrefix(int[] nums) {
        int pre = 0;    // 前缀和, 初始为0
        int max = Integer.MIN_VALUE;    // 记录子数组最大值
        for(int i = 0; i < nums.length; i++) {
            if(pre < 0) {
                pre = 0;
            }
            pre += nums[i];
            max = Math.max(max, pre);
        }
        return max;
    }
}

解法二: 动态规划

前面我们说过在解决最优解问题时往往可以考虑动态规划, 那么本题该如何使用动态规划来解决?

核心还是将全局最优分解为局部最优。我们用dp[i]表示以 nums[i] 结尾的的最大子数组和, 那么对于dp[i+1] ,如果dp[i] 为正数, dp[i+1] 的值为nums[i+1]+dp[i]。 如果dp[i]为负数, dp[i+1]的值就直接取nums[i+1] 的值, 结果我们取dp[nums.length-1]就行。

public class maxSumSubArray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(getMaxSubArraySumByDynamic(nums));
    }
    // 动态规划解决思路:
    // 1.定义dp[i] 表示以nums[i]结尾的最大子数组和
    // 2.dp[i] = max(nums[i], dp[i-1]+nums[i])
    // 3.最后返回dp
    public static int getMaxSubArraySumByDynamic(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}