Last updated on January 19th, 2025 at 05:51 pm

Here, we see a Maximum Subarray LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array

Companies

Google, Microsoft, Uber

Level of Question

Medium

Maximum Subarray LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Kadane’s Algorithm. This is a well-known algorithm for solving the Maximum Subarray Problem, which involves finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

It is a Dynamic Programming approach that uses a greedy strategy to solve the problem in linear time.

3. Code Implementation in Different Languages

3.1 Maximum Subarray C++

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

3.2 Maximum Subarray Java

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

3.3 Maximum Subarray JavaScript

var maxSubArray = function(nums) {
  var prev = 0;
  var max = -Number.MAX_VALUE;
  for (var i = 0; i < nums.length; i++) {
    prev = Math.max(prev + nums[i], nums[i]);
    max = Math.max(max, prev);
  }
  return max;    
};

3.4 Maximum Subarray Python

class Solution(object):
    def maxSubArray(self, nums):
        if not nums:
            return 0
        curSum = maxSum = nums[0]
        for num in nums[1:]:
            curSum = max(num, curSum + num)
            maxSum = max(maxSum, curSum)
        return maxSum

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)