Maximum Subarray LeetCode Solution | Easy Approach

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.

A subarray is a contiguous part of an array.

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 <= 105
• -104 <= nums[i] <= 104

Maximum Subarray Solutions

✅Time: O(n)
✅Space: O(1)

C++

class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN;
    int sum = 0;

    for (const int num : nums) {
      sum += num;
      ans = max(ans, sum);
      sum = max(sum, 0);
    }

    return ans;
  }
};
 

Java

 class Solution {
  public int maxSubArray(int[] nums) {
    int ans = Integer.MIN_VALUE;
    int sum = 0;

    for (final int num : nums) {
      sum += num;
      ans = Math.max(ans, sum);
      sum = Math.max(sum, 0);
    }

    return ans;
  }
}

 

Python

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    ans = -math.inf
    summ = 0

    for num in nums:
      summ += num
      ans = max(ans, summ)
      summ = max(summ, 0)

    return ans

Watch Tutorial

Checkout more Solutions here