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