Home Maximum Subarray
Post
Cancel

LeetCode #53: Maximum Subarray (C/C++).

medium

source: https://leetcode.com/problems/maximum-subarray/
C/C++ Solution to LeetCode problem 53. Maximum Subarray.

Problem


Given an integer array nums, find the subarray with the largest sum, and return its sum.

Examples


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

Solution


For this problem, we will use Dynamic Programming.

  • Iterate through each number:
  • Keep tracking of the sum of elements.
  • If at any point the sum < 0 it is not adding to the result, so, we can reset the sum = 0.
  • Update the maximum found.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int sum = 0; 
    int maxSum = INT_MIN;
    int j = 0;
    
    while (j<nums.size()) {
      if (sum < 0 && nums[j] >= sum)
        sum = 0;
      
      sum += nums[j];
      maxSum = max(maxSum, sum);
      j++;
    }
    return maxSum;
  }
};
This post is licensed under CC BY 4.0 by the author.

Edit Distance

Spiral Matrix