Maximum Subarray

---

Maximum Subarray: Given an integer array nums, find the subarray 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 = [5,4,-1,7,8]
Output: 23

---

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

---

Try this Problem on your own or check similar problems:

1. Maximum Product Subarray
2. Best Time To Buy And Sell Stock
3. Degree of an Array

Solution:

Java

public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE, sum = 0;
    for(int i = 0; i < nums.length; ++i){
        sum = Math.max(nums[i], nums[i] + sum);
        maxSum = Math.max(sum, maxSum);
    }
    return maxSum;
}

JavaScript

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

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = float('-inf')
        sum = 0
        for i in range(len(nums)):
            sum = max(nums[i], nums[i] + sum)
            maxSum = max(sum, maxSum)
        return maxSum

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum = max(nums[i], nums[i] + sum);
            maxSum = max(sum, maxSum);
        }
        return maxSum;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

The key to solving this problem is to understand that because of negative numbers in the input array, our sum is not increasing by every iteration, and at each element we have choice to make:

• use only that element and omit the contribution from the sum[0...i-1] (it could be that all 0..i-1 element are negative so it's better for us to only use nums[i] if it's the first positive).
• use the ever-increasing sum nums[i] + sum.

At the end we just return maxSum.