Maximum Subarray Leetcode Solution

In this post, we are going to solve the Maximum Subarray Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Problem

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

Now, let’s see the leetcode solution of Maximum Subarray Leetcode Solution.

Maximum Subarray Leetcode Solution in 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

Maximum Subarray Leetcode Solution in CPP

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;
  }
};

Maximum Subarray Leetcode Solution in 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;
  }
}

Note: This problem Maximum Subarray is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

NEXT: Spiral Matrix