Skip to content

4.MaxSubarraySum.md

Latest commit

 

History

History
226 lines (158 loc) · 5.42 KB

4.MaxSubarraySum.md

File metadata and controls

226 lines (158 loc) · 5.42 KB

🐬 Maximum Subarray Sum - Kadane's Algorithm

📋 Problem Statement

Given an integer array arr of length n, find the sum of the contiguous subarray (of at least one element) which has the largest sum.

🔎 Examples

Input Output Explanation
[-2,1,-3,4,-1,2,1,-5,4] 6 Subarray [4,-1,2,1] has sum 6.
[1,2,3,4] 10 Entire array sum is 10.
[-1,-2,-3] -1 Single element -1 is the maximum sum.

🐢 Brute-Force Approaches

1️⃣ O(n³) Triple Loop

  • Compute all possible subarrays by choosing start i and end j, then summing in an inner loop.
  • Track the maximum.
int maxSubarrayBrute3(const vector<int>& arr) {
    int n = arr.size(), best = INT_MIN;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            int sum = 0;
            for (int k = i; k <= j; ++k)
                sum += arr[k];
            best = max(best, sum);
        }
    }
    return best;
}
  • Time: O(n³)
  • Space: O(1)

2️⃣ O(n²) Prefix‐Sum Optimization

  • Precompute prefix sums P[k] = sum(arr[0…k-1]).
  • Compute subarray sum in O(1): sum(i…j) = P[j+1] – P[i].
  • Double loop for (i,j) → O(n²).
int maxSubarrayBrute2(const vector<int>& arr) {
    int n = arr.size(), best = INT_MIN;
    vector<int> P(n+1, 0);
    for (int i = 0; i < n; ++i)
        P[i+1] = P[i] + arr[i];
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            best = max(best, P[j+1] - P[i]);
        }
    }
    return best;
}
  • Time: O(n²)
  • Space: O(n)

✨ Optimal Approach: Kadane’s Algorithm (O(n) Time, O(1) Space)

Intuition

Maintain two variables as you scan:

  • current_sum = maximum sum of a subarray ending at the current index.
  • max_sum = overall maximum subarray sum seen so far.

At each element x = arr[i]:

  1. Extend or restart:

    current_sum = max(x, current_sum + x)

    – either start a new subarray at x, or extend the previous one.

  2. Update the global max:

    max_sum = max(max_sum, current_sum)

📝 Algorithm

FUNCTION Kadane(arr, n):
    max_sum ← arr[0]
    current_sum ← 0

    FOR i FROM 0 TO n-1:
        current_sum ← current_sum + arr[i]
        IF current_sum > max_sum:
            max_sum ← current_sum
        IF current_sum < 0:
            current_sum ← 0

    RETURN max_sum
  • We reset current_sum to 0 whenever it becomes negative, since any further extension would only decrease future sums.

💻 C++ Code

#include <bits/stdc++.h>
using namespace std;

/**
 * Returns the largest sum of any contiguous subarray.
 */
int Kadane(const vector<int>& arr) {
    int max_sum = INT_MIN;
    int current_sum = 0;

    for (int x : arr) {
        current_sum += x;
        max_sum = max(max_sum, current_sum);
        if (current_sum < 0)
            current_sum = 0;
    }
    return max_sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << Kadane(arr) << "\n";
    return 0;
}

🧮 Dry Run Example

For arr = [-2,1,-3,4,-1,2,1,-5,4]:

i x current_sum max_sum Explanation
0 -2 -2→0 0? vs -2 → 0 reset at negative
1 1 1 max(0,1)=1 start new subarray
2 -3 -2→0 1 reset
3 4 4 4
4 -1 3 4
5 2 5 5
6 1 6 6 best
7 -5 1 6
8 4 5 6

Result: 6

📈 Complexity Analysis

Metric Value
Time Complexity O(n)
Space Complexity O(1)

Kadane’s algorithm scans the array once, using two integer accumulators.

📎 Notes & Facts

  • All Negative Array: Kadane still works—max_sum becomes the largest (least negative) element, since we never reset before updating.

  • Empty Array: By problem definition n ≥ 1. If n=0, handle separately.

  • Variants:

    • Track start/end indices to reconstruct the subarray.
    • 2D Kadane for maximum-sum rectangle in a matrix (O(n³)).

❓ FAQs

Q1: Why reset current_sum to zero on negative?

A negative running sum would only decrease any future subarray sum; better to start fresh at the next element.

Q2: Can Kadane handle zeros?

Yes—zeros neither reset nor increase it unduly; they behave neutrally.

Q3: How to get the actual subarray (not just sum)?

Track start, end, and a temporary s index:

  • When you reset current_sum, set s = i+1.
  • When you update max_sum, record (start=s, end=i).

Q4: What if you need at least length L?

Use a deque or prefix sums with sliding-window minimum to enforce length constraints.