Problem Statement
Given an integer array nums, return the maximum possible sum of a non-empty contiguous subarray.
A contiguous subarray contains consecutive elements from the original array.
Return 0 when nums is empty.
Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has the maximum sum 6.
Example 2
Input: nums = [-5, -2, -8, -1]
Output: -1
Explanation: All elements are negative, so the maximum subarray is [-1].
Brute Force Approach
The simplest idea is to generate every possible contiguous subarray and calculate the sum of each one.
Every pair of starting and ending indices identifies one valid subarray. Checking all such ranges guarantees the correct answer, but many overlapping ranges repeatedly add the same elements.
Algorithm
Store the array size in
n. Ifn == 0, return0because no non-empty subarray can be formed.Initialize
maxSumwithnums[0], ensuring that an array containing only negative values still returns a valid non-empty subarray sum.Treat every index
startas the beginning of a possible subarray and every indexendfromstartton - 1as its ending position.For each selected range
[start, end], initializecurrentSumwith0and traverse the complete range to calculate its sum.Compare the calculated
currentSumwithmaxSumand updatemaxSumwhenever the current subarray produces a larger sum.Return
maxSumafter every possible contiguous subarray has been examined.
Dry Run
Maximum Subarray sum Brute Force.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: long long maxSubarraySum(vector<int>& nums) { int n = nums.size(); // No non-empty subarray exists. if (n == 0) { return 0; } long long maxSum = nums[0]; /* * Generate every possible subarray * using its start and end indices. */ for (int start = 0; start < n; start++) { for (int end = start; end < n; end++) { long long currentSum = 0; // Calculate the sum of the selected range. for (int index = start; index <= end; index++) { currentSum += nums[index]; } // Keep the largest subarray sum found so far. if (currentSum > maxSum) { maxSum = currentSum; } } } return maxSum; }};int main() { vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; Solution solution; cout << solution.maxSubarraySum(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N³), where N represents the array size. Two loops select the starting and ending indices, while a third traversal calculates the sum of every selected range.
Space Complexity: O(1), because only index variables, currentSum, and maxSum require auxiliary storage.
Better Approach
The Brute Force Approach wastes time by recalculating the complete sum whenever the ending position changes.
For a fixed starting index, the next subarray differs only by one additional element. Keeping a running sum allows that new element to be added directly instead of calculating the whole range again.
Algorithm
Store the array size in
n. If the array is empty, return0.Initialize
maxSumwithnums[0]so that negative-only arrays are handled correctly.Treat every index
startas the beginning of a new group of subarrays and initializecurrentSumwith0for that starting position.Move
endfromstartton - 1and addnums[end]tocurrentSum. This reuses the previous range sum instead of calculating the complete subarray again.Compare
currentSumwithmaxSumafter every extension because each updated sum represents a valid subarray fromstarttoend.Return
maxSumafter all starting and ending positions have been processed.
Dry Run
Maximum Subarray sum Better.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: long long maxSubarraySum(vector<int>& nums) { int n = nums.size(); // No non-empty subarray exists. if (n == 0) { return 0; } long long maxSum = nums[0]; for (int start = 0; start < n; start++) { long long currentSum = 0; /* * Extend the current subarray one element * at a time instead of recalculating its sum. */ for (int end = start; end < n; end++) { currentSum += nums[end]; // Keep the best sum among all ranges seen so far. if (currentSum > maxSum) { maxSum = currentSum; } } } return maxSum; }};int main() { vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; Solution solution; cout << solution.maxSubarraySum(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N²), where N represents the array size. Every starting position expands through all possible ending positions, while each expansion requires only one addition.
Space Complexity: O(1), because only loop indices, currentSum, and maxSum require auxiliary storage.
Optimal Approach
At every position, the main question is whether the previous subarray still helps.
Only two choices matter: extend the best subarray ending at the previous position, or leave that subarray behind and start fresh from the current element. A harmful previous sum should not be carried forward because it can only reduce the new total.
This decision at every index allows the maximum sum to be found in a single traversal.
Algorithm
Store the array size in
n. Ifn == 0, return0.Initialize both
currentSumandmaxSumwithnums[0]. Here,currentSumstores the best subarray sum ending at the current position, whilemaxSumstores the best sum found anywhere so far.Traverse from index
1, since the first element has already been used to initialize both values.At each index, choose the larger of
nums[index]andcurrentSum + nums[index]. Starting fromnums[index]discards the previous subarray when carrying it forward would reduce the sum.Compare the updated
currentSumwithmaxSumand updatemaxSumwhenever the current ending position produces a better overall result.Return
maxSumafter every element has been processed.
Dry Run
Maximum Subarray sum Optimal .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: long long maxSubarraySum(vector<int>& nums) { int n = nums.size(); // No non-empty subarray exists. if (n == 0) { return 0; } long long currentSum = nums[0]; long long maxSum = nums[0]; for (int index = 1; index < n; index++) { /* * Start fresh when carrying the previous * subarray would give a smaller sum. */ currentSum = max( (long long) nums[index], currentSum + nums[index] ); // Record the best sum found anywhere so far. if (currentSum > maxSum) { maxSum = currentSum; } } return maxSum; }};int main() { vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; Solution solution; cout << solution.maxSubarraySum(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the array size. Every element receives one constant-time decision.
Space Complexity: O(1), because only currentSum and maxSum require auxiliary storage.
FAQs
Q1. Why must maxSum be initialized with nums[0] instead of 0?
Initializing with 0 would incorrectly return 0 for an array containing only negative values. Using nums[0] ensures that the answer always represents a valid non-empty subarray.
Q2. What exactly does currentSum represent in Kadane’s Algorithm?
currentSum represents the maximum possible sum of a contiguous subarray that must end at the current index. The restriction is important because the next element can only extend a subarray ending immediately before it.
Q3. Why is it safe to discard the previous subarray when starting fresh gives a larger sum?
Any future subarray containing the current element would become smaller by carrying a harmful previous sum. Discarding that contribution cannot remove a better future answer.
Q4. How can Kadane’s Algorithm return the actual subarray instead of only the maximum sum?
Track a temporary starting index whenever a fresh subarray begins. Whenever maxSum improves, store the current start and ending index as the best range.
Q5. How does the problem change when an empty subarray is allowed?
When an empty subarray is allowed, the answer can be 0. In that variation, maxSum may be initialized with 0, and an all-negative array returns the empty subarray instead of the largest negative element.
Be the first to add a comment.