Question

Formatted question description: https://leetcode.ca/all/53.html

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

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.

Algorithm

The O(n) solution is to define two variables res and curSum, where res holds the final result to be returned, that is, the sum of the largest sub-array.

The initial value of curSum is 0, and each traversal of a number num, compare curSum + num and num. Store the larger value in curSum, and then store the larger value in res and curSum in res, and so on until the entire array is traversed, and the value of the largest sub-array can be obtained in res.

Code

public class Maximum_Subarray {

	// o(N)
	public class Solution_oN {
		public int maxSubArray(int[] nums) {
			int res = Integer.MIN_VALUE, curSum = 0;
			for (int num : nums) {
				// like a 1D dp[i], 'curSum' is max sum up to index-i
				// if 'curSum' is <0 , then it will be num
				curSum = Math.max(curSum + num, num);
				res = Math.max(res, curSum);
			}
			return res;
		}
	}

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

			if (nums == null || nums.length == 0) {
				return 0;
			}

			// consider input: [-1,-2,-3], and [-3,-2,-1]
			int max = nums[0];

			int tmpSum = nums[0]; // @note: cannot set to 0
			for (int i = 1; i < nums.length; i++) {
				if (tmpSum < 0) { // even if current number is large positive on, this tmpSum makes no contribution
					tmpSum = nums[i];
				} else {
					tmpSum += nums[i];
				}

				max = Math.max(max, tmpSum);

			}

			return max;
		}

	}

	public class Solution_divide_conquer {

		/* O(n logn), still better than brute force O(n^2)

		Time analysis:

		1. Find-Max-Cross-Subarray: O(n) time
		2. Two recursive calls on input size n/2

		Thus:
			T(n) = 2T(n/2) + O(n)
			T(n) = O(n log n)

		*/
		public int maxSubArray(int[] nums) {

			if (nums == null || nums.length == 0) {
				return 0;
			}

			return dfs(nums, 0, nums.length - 1);
		}

		private int dfs(int[] nums, int start, int end) {

			if (start == end) {
				return nums[start];
			}

			int mid = (start + end) >> 1; // @note: possible overflow

			int left = dfs(nums, start, mid);
			int right = dfs(nums, mid + 1, end);

			int leftHalf = 0, rightHalf = 0;

			int leftMax = Integer.MIN_VALUE;
			int rightMax = Integer.MIN_VALUE;

			for (int i = mid + 1; i <= end; i++) {
				rightHalf += nums[i];
				rightMax = Math.max(rightHalf, rightMax);
			}

			for (int i = mid; i >= start; i--) {
				leftHalf += nums[i];
				leftMax = Math.max(leftMax, leftHalf);
			}

			return Math.max(rightMax + leftMax, Math.max(left, right));
		}
	}

}

############

class Solution {
    public int maxSubArray(int[] nums) {
        int f = nums[0], res = nums[0];
        for (int i = 1, n = nums.length; i < n; ++i) {
            f = nums[i] + Math.max(f, 0);
            res = Math.max(res, f);
        }
        return res;
    }
}

// OJ: https://leetcode.com/problems/maximum-subarray/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        partial_sum(nums.begin(), nums.end(), nums.begin());
        int minSum = 0, ans = INT_MIN;
        for (int n : nums) {
            ans = max(ans, n - minSum);
            minSum = min(minSum, n);
        }
        return ans;
    }
};

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = cur_sum = nums[0]
        for num in nums[1:]:
            cur_sum = num + max(cur_sum, 0)
            res = max(res, cur_sum)
        return res

############

class Solution(object):
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) == 0:
      return 0
    preSum = maxSum = nums[0]
    for i in range(1, len(nums)):
      preSum = max(preSum + nums[i], nums[i])
      maxSum = max(maxSum, preSum)
    return maxSum

func maxSubArray(nums []int) int {
    f, res := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if f > 0 {
            f += nums[i]
        } else {
            f = nums[i]
        }
        if f > res {
            res = f
        }
    }
    return res
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let f = nums[0],
        res = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        f = nums[i] + Math.max(f, 0);
        res = Math.max(res, f);
    }
    return res;
};

public class Solution {
    public int MaxSubArray(int[] nums) {
        int res = nums[0], f = nums[0];
        for (int i = 1; i < nums.Length; ++i)
        {
            f = nums[i] + Math.Max(f, 0);
            res = Math.Max(res, f);
        }
        return res;
    }
}

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = nums[0];
        let mut sum = nums[0];
        for i in 1..n {
            let num = nums[i];
            sum = num.max(sum + num);
            res = res.max(sum);
        }
        res
    }
}

function maxSubArray(nums: number[]): number {
    let [ans, f] = [nums[0], nums[0]];
    for (let i = 1; i < nums.length; ++i) {
        f = Math.max(f, 0) + nums[i];
        ans = Math.max(ans, f);
    }
    return ans;
}

53 - Maximum Subarray

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions