📅 Date: Feb 11, 2026
🔥 Topic: Maximum Subarray Sum (Kadane’s Algorithm)

🤔 The Problem

Given an array, find the contiguous sub-array (continuous part) which has the largest sum.
Arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
If I check all possibilities, it takes O(n²). We need something faster.

💡 The Idea (O(n))

Kadane’s Logic: "If a train carriage has negative people (sum < 0), detach it and start a new train."

1. Keep adding elements to `currentSum`.
2. If `currentSum` becomes higher than `maxSum`, update `maxSum`.
3. If `currentSum` drops below 0, reset it to 0 (because a negative start will only decrease our future sum).

📊 Dry Run Table

Arr: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Element Current Sum Max Sum Action
-2 -2 -> 0 -2 Reset to 0
1 1 1 Update Max
-3 -2 -> 0 1 Reset to 0
4 4 4 Update Max
-1 3 4 Continue
2 5 5 Update Max
1 6 6 Update Max (Ans)

💻 Day 41 Code

#include <iostream>
#include <vector>
#include <climits> // For INT_MIN
using namespace std;

int maxSubArray(vector<int>& nums) {
    int maxSum = INT_MIN;
    int currentSum = 0;

    for(int val : nums) {
        currentSum += val;
        
        if(currentSum > maxSum) {
            maxSum = currentSum;
        }
        
        if(currentSum < 0) {
            currentSum = 0; // The Reset Trick
        }
    }
    return maxSum;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Maximum Sum is: " << maxSubArray(arr) << endl;
    return 0;
}

💭 Thoughts

The beauty of this algorithm is that it makes a decision at every step without looking back. O(n) complexity makes it lightning fast!