Array Presets
Algorithm Loop
The Power of O(N)
We maintain a running Current Sum. If it ever drops
below 0, the contiguous subarray is "dragging us
down", so we reset it back to 0 and start fresh from the next element.
Meanwhile, Max Sum blindly tracks the highest peak
we ever reach!
Live Console Log
Current Sum
Max Sum
Kadane's Algorithm
Kadane's Algorithm is an elegant Dynamic Programming algorithm used to find the contiguous subarray with the largest sum within a one-dimensional numeric array. It achieves this in $O(N)$ Time and $O(1)$ Space.
The Local Maximum
At each step, we calculate the current_sum. The core intuition is: if the
current accumulated sum ever drops below zero, the entire prefix is a net negative. It is
better to discard the prefix completely and start a new subarray from the next element
(resetting current_sum to 0).
The Global Maximum
We blindly maintain a max_sum variable. At every single element, regardless of
whether current_sum is positive or negative, we check if
current_sum > max_sum. If it is, we update our global record. This ensures we
don't miss the peak before a reset occurs.
Algorithm Implementation
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int i = 0; i < nums.length; i++) {
// Step 1: Add current element to running sum
currentSum += nums[i];
// Step 2: Did we hit a new global maximum?
if (currentSum > maxSum) {
maxSum = currentSum;
}
// Step 3: If running sum is negative, discard it
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
int currentSum = 0;
for (int i = 0; i < nums.size(); i++) {
currentSum += nums[i];
maxSum = max(maxSum, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
};class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf')
current_sum = 0
for num in nums:
current_sum += num
if current_sum > max_sum:
max_sum = current_sum
if current_sum < 0:
current_sum = 0
return max_sum