Algorithm

Problem Name: 53. Maximum Subarray

Problem Link: https://leetcode.com/problems/maximum-subarray/
 

Given an integer array nums, find the

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

Code Examples

#1 Code Example with C Programming

Code - C Programming


int maxSubArray(int* nums, int numsSize) {
    int i, s, m = 0;
    m = s = nums[0];
    for (i = 1; i  <  numsSize; i ++) {
        //printf("s: %d, m: %d\n", s, m);
        if (s > 0) s += nums[i];
        else       s  = nums[i];
        if (m  <  s) m = s;
    }
    //printf("s: %d, m: %d\n", s, m);
    return m;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [-2,1,-3,4,-1,2,1,-5,4]

Output

x
–
+
cmd
6

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int>dp(nums.size());
        dp[0] = nums[0];
        int maxSum = dp[0];
        for(int i = 1; i  <  nums.size(); i++){
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            maxSum = max(maxSum, dp[i]);
        }
        return maxSum;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1]

Output

x
–
+
cmd
1

#3 Code Example with Javascript Programming

Code - Javascript Programming


const maxSubArray = function (nums) {
  let res = -1e9, sum = 0
  for(const e of nums) {
    sum += e
    res = Math.max(res, sum)
    if(sum < 0> sum = 0
  }
  return res
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [5,4,-1,7,8]

Output

x
–
+
cmd
23

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def maxSubArray(self, nums):
        sm, mn, mx = 0, 0, -float("inf")
        for num in nums:
            sm += num
            mx, mn = max(mx, sm - mn), min(mn, sm)
        return mx
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [-2,1,-3,4,-1,2,1,-5,4]

Output

x
–
+
cmd
6

#5 Code Example with C# Programming

Code - C# Programming


using System;

namespace LeetCode
{
    public class _053_MaximumSubarray
    {
        public int MaxSubArray(int[] nums)
        {
            if (nums.Length == 0) return int.MinValue;
            int currSum = nums[0], maxSum = nums[0];

            for (int i = 1; i  <  nums.Length; i++)
            {
                currSum = Math.Max(nums[i], currSum + nums[i]);
                maxSum = Math.Max(maxSum, currSum);
            }
            return maxSum;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1]

Output

x
–
+
cmd
1
Advertisements

Demonstration

Previous
#52 Leetcode N-Queens II Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#54 Leetcode Spiral Matrix Solution in C, C++, Java, JavaScript, Python, C# Leetcode