53. Maximum Subarray

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Code

class Solution {
    public int maxSubArray(int[] nums) {

        int max = nums[0];

        int dp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 如果dp<0就放弃dp
            dp = Math.max(dp + nums[i], nums[i]);
            max = Math.max(max, dp);
        }

        return max;
    }
}

O(n) O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int res = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        for(int i = 1; i < nums.length; i++){
            dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

divide and conquer 解法, 并不是最优解

class Solution {
    private int[] numsArray;

    public int maxSubArray(int[] nums) {
        numsArray = nums;

        // Our helper function is designed to solve this problem for
        // any array - so just call it using the entire input!
        return findBestSubarray(0, numsArray.length - 1);
    }

    private int findBestSubarray(int left, int right) {
        // Base case - empty array.
        if (left > right) {
            return Integer.MIN_VALUE;
        }

        int mid = (left + right) / 2;
        int curr = 0;
        int bestLeftSum = 0;
        int bestRightSum = 0;

        // Iterate from the middle to the beginning.
        for (int i = mid - 1; i >= left; i--) {
            curr += numsArray[i];
            bestLeftSum = Math.max(bestLeftSum, curr);
        }

        // Reset curr and iterate from the middle to the end.
        curr = 0;
        for (int i = mid + 1; i <= right; i++) {
            curr += numsArray[i];
            bestRightSum = Math.max(bestRightSum, curr);
        }

        // The bestCombinedSum uses the middle element and the best
        // possible sum from each half.
        int bestCombinedSum = numsArray[mid] + bestLeftSum + bestRightSum;

        // Find the best subarray possible from both halves.
        int leftHalf = findBestSubarray(left, mid - 1);
        int rightHalf = findBestSubarray(mid + 1, right);

        // The largest of the 3 is the answer for any given input array.
        return Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf));
    }
}

time: nlog(n) space: log(n)

打印 subarray 要求 subarray 的长度至少是 2

class Solution {

    public List<Integer> maxSumWithK(int nums[], int k) {
        int n = nums.length;
        int maxSum[] = new int[n];
        // 记录开始和结束的位置
        int maxStart[] = new int[n];

        maxSum[0] = nums[0];
        int dp = nums[0];
        int start = 0;
        for (int i = 1; i < n; i++) {
            if (dp < 0) {
                maxStart[i] = i;
                dp = nums[i];
            } else {
                dp += nums[i];
                maxStart[i] = start;
            }

            maxSum[i] = dp;
        }

        // Sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        // sliding window
        // 确保有k这么长的window, 然后看加上maxSum是否结果会变大
        int result = sum;
        int resStart = 0;
        int resEnd = k;
        for (int i = k; i < n; i++) {
            // Compute sum of k elements ending with a[i].
            // i ~ i + k
            sum = sum + nums[i] - nums[i - k];

            // Update result if required
            if (sum > result) {
                resStart = i - k;
                resEnd = i;
                result = sum;
            }

            if (sum + maxSum[i - k] > result) {
                resStart = maxStart[i - k];
                resEnd = i;
                result = sum + maxSum[i - k];
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = resStart; i < resEnd; i++) {
            res.add(nums[i]);
        }

        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> res = solution.maxSumWithK(new int[]{-1, 2, -100, 10, -300}, 3);
        System.out.println(res);
    }
}