42-连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

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

示例

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

暴力解法

我们可以枚举出数组的所有子数组。长度为n的数组，子数组数量是n(n+1)/2，时间复杂度是o(n^2)

分而治之

假如我们找到了这样的一个连续子数组，那么它肯定是以下三个位置之一：

子数组

我们将数组分成两部分，那么最终的子数组肯定要么在左侧数组，要么在右侧数组，要么就是在中间。

所以我们采用分治的思路，对问题进行缩小，最后在合并结果。

public int FindGreatestSumOfSubArray2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int maxSum = find(array, 0, array.length - 1);
        return maxSum;

    }

    private int find(int[] array, int lo, int hi) {
        if (lo >= hi) {
            return array[lo];
        }
        int middle = (hi - lo) / 2 + lo;
        int maxLeftSum = find(array, lo, middle);
        int maxRightSum = find(array, middle + 1, hi);
        int maxLeftSumWithBorder = array[middle];
        int maxRightSumWithBorder = array[middle + 1];

        if (lo < middle) {
            int cur = 0;
            for (int i = middle; i >= lo; i--) {
                cur += array[i];
                if (cur > maxLeftSumWithBorder) {
                    maxLeftSumWithBorder = cur;
                }
            }
        }
        if (hi > middle) {
            int cur = 0;
            for (int i = middle+1; i <= hi; i++) {
                cur += array[i];
                if (cur > maxRightSumWithBorder) {
                    maxRightSumWithBorder = cur;
                }
            }
        }
        return max(max(maxLeftSum, maxRightSum), maxLeftSumWithBorder + maxRightSumWithBorder);
    }

    private int max(int a, int b) {
        return a > b ? a : b;
    }

动态规划

递推公式

我们用f(i)表示以第i个元素为结尾的子数组的最大和。

当i=0时，显然f(0) = p[0]

当i > 0时，

​ 假如f(i-1) < 0, 说明以i-1元素为结尾的子数组是负数，那么就取p[i]就行。

​ 假如f(i-1) > 0 这时可以取f(i-1)+p[i] $$ f(i)= \begin{cases} p[i], & \text {if i=0 或者 $f(i-1)$<0} \ f(i-1)+p[i], & \text{if i!=0或者$f(i-1)>0$} \end{cases} $$

public int maxSubArray3(int[] nums) {
        int max = Integer.MIN_VALUE;
        int curSum = 0;
        for (int num : nums) {
            if (curSum <= 0) {
                curSum = num;
            }else{
                curSum += num;
            }
            max = Math.max(curSum, max);
        }
        return max;
}

使用备忘录

private Map<Integer, Integer> memo = new HashMap<>();
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, maxSubArrayCore(nums, i));
        }
        return max;
    }
		// 计算以start为开头的连续数组的最大和
    public int maxSubArrayCore(int[] nums, int start) {
        if (start == nums.length - 1) {
            return nums[start];
        }
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        //最大值的是{nums[start],以start+1为起点的连续数组的最大和+nums[start]}中的较大值
        int max = Math.max(nums[start], maxSubArrayCore(nums, start + 1) + nums[start]);
        memo.put(start, max);
        return max;
    }