53. Maximum Subarray

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

 

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-100000]
Output: -100000

 

Constraints:

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

 

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. 

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public class Solution { public int maxSubArray(int[] nums) { // answer before 2021 // int globalMax = nums[0]; // int localMax = nums[0]; // for (int i = 1; i < nums.length; i ++) { // // localMax is the bigger value which includes "i"th number, so that the globalMax can be the result of contiguous subarray // localMax = Math.max(nums[i], localMax + nums[i]); // globalMax = Math.max(globalMax, localMax); // } // return globalMax; // answer on 2021 if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } // dp is the value where max sum given i th element must be included int[] dp = new int[nums.length]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i ++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); } int maxSum = dp[0]; for (int i = 1; i < dp.length; i ++) { maxSum = Math.max(maxSum, dp[i]); } return maxSum; } }

Regarding the follow up via Divide and Conqure: below answer is from Leetcode forum. 

Divide and Conquer

The Divide-and-Conquer algorithm breaks nums into two halves and find the maximum subarray sum in them recursively. Well, the most tricky part is to handle the case that the maximum subarray spans the two halves. For this case, we use a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArray(nums, 0, nums.size() - 1);
    }
private:
    int maxSubArray(vector<int>& nums, int l, int r) {
        if (l > r) {
            return INT_MIN;
        }
        int m = l + (r - l) / 2, ml = 0, mr = 0;
        int lmax = maxSubArray(nums, l, m - 1);
        int rmax = maxSubArray(nums, m + 1, r);
        for (int i = m - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            ml = max(sum, ml);
        }
        for (int i = m + 1, sum = 0; i <= r; i++) {
            sum += nums[i];
            mr = max(sum, mr);
        }
        return max(max(lmax, rmax), ml + mr + nums[m]);