Kadane’s Algorithm

159
0

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. If n == 0, return 0 because no non-empty subarray can be formed.

  • Initialize maxSum with nums[0], ensuring that an array containing only negative values still returns a valid non-empty subarray sum.

  • Treat every index start as the beginning of a possible subarray and every index end from start to n - 1 as its ending position.

  • For each selected range [start, end], initialize currentSum with 0 and traverse the complete range to calculate its sum.

  • Compare the calculated currentSum with maxSum and update maxSum whenever the current subarray produces a larger sum.

  • Return maxSum after every possible contiguous subarray has been examined.

Dry Run

Maximum Subarray sum Brute Force.png

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, return 0.

  • Initialize maxSum with nums[0] so that negative-only arrays are handled correctly.

  • Treat every index start as the beginning of a new group of subarrays and initialize currentSum with 0 for that starting position.

  • Move end from start to n - 1 and add nums[end] to currentSum. This reuses the previous range sum instead of calculating the complete subarray again.

  • Compare currentSum with maxSum after every extension because each updated sum represents a valid subarray from start to end.

  • Return maxSum after all starting and ending positions have been processed.

Dry Run

Maximum Subarray sum Better.png

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. If n == 0, return 0.

  • Initialize both currentSum and maxSum with nums[0]. Here, currentSum stores the best subarray sum ending at the current position, while maxSum stores 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] and currentSum + nums[index]. Starting from nums[index] discards the previous subarray when carrying it forward would reduce the sum.

  • Compare the updated currentSum with maxSum and update maxSum whenever the current ending position produces a better overall result.

  • Return maxSum after every element has been processed.

Dry Run

Maximum Subarray sum Optimal .png

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.

ArraysTCS NQT

Read Similar Blogs

Comments0