Kadane's Algorithm

Kadane's Algorithm

Kadane’s Algorithm is a popular and efficient algorithm used to solve the "Maximum Subarray Sum" problem — that is, finding the contiguous subarray (with at least one element) in an array that has the largest sum

🧠 Problem Statement:

Given an array of integers (positive, negative, or both), find the maximum sum of a contiguous subarray.

OR

OR

🎯 Goal

1. Find two numbers that add up to a given target.
2. For each number, find target - current number.
3. Check if this value exists elsewhere in the array.
4. If found, return the indices. -->

🔍 Kadane’s Algorithm - Step-by-Step Explanation

Let’s break it down with a step-by-step example and an explanation.

✅ Idea:
The algorithm iterates through the array while maintaining:

1. current_sum: The maximum sum of the subarray ending at the current index.

2. max_sum: The overall maximum sum encountered so far.

📌 Step-by-Step Algorithm:

Initialize:

current_sum = arr[0]
max_sum = arr[0]

This means: initially, both the current sum and the max sum are set to the first element of the array.

Loop through the array from index 1 to n-1:

for i = 1 to n-1:
    current_sum = max(arr[i], current_sum + arr[i])Kadane's Algorithm 
    max_sum = max(max_sum, current_sum)

Why?

• current_sum + arr[i]: Extending the previous subarray.

• arr[i]: Starting a new subarray from the current index.

• We choose whichever gives a larger sum.

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

Let’s go through the array:

🔚 Final answer: max_sum = 6

The maximum subarray is [4, -1, 2, 1].

✅ Complete Code (Python):

def kadane(arr):
    current_sum = max_sum = arr[0]

    for i in range(1, len(arr)):
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

✅ Java Version

public class Kadane {
    public static int kadane(int[] arr) {
        int current_sum = arr[0];
        int max_sum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            current_sum = Math.max(arr[i], current_sum + arr[i]);
            max_sum = Math.max(max_sum, current_sum);
        }

        return max_sum;
    }


    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + kadane(arr));
    }
}

✅ C++ Version

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kadane(vector<int>& arr) {
    int current_sum = arr[0];
    int max_sum = arr[0];

    for (int i = 1; i < arr.size(); i++) {
        current_sum = max(arr[i], current_sum + arr[i]);
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

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

⏱️ Time Complexity:

• O(n) — We go through the array only once.

• 🧠 Space Complexity:
  O(1) — We use only two variables: current_sum and max_sum.

📌 Applications of Kadane's Algorithm

1. Stock Market Analysis:

   • To find the best time to buy and sell a stock for maximum profit,
     assuming daily profit/loss data.

2. Financial Forecasting:

   • Identifying periods of maximum financial growth or minimum losses
     using daily/weekly revenue or cost data.

3. Game Development:

   • Scoring systems where you need to determine the best sequence
     of moves or attacks that yield maximum points.

4. Data Compression / Signal Processing:

   • Detecting regions of strongest signal or compression blocks with
     highest intensity in 1D arrays.

5. Temperature / Weather Patterns:

   • Identifying longest warm streaks or periods of consistent improvement
     based on daily temperature changes.

6. Competitive Programming / Interviews:

   • One of the most frequently asked problems in technical interviews
     for optimizing subarray-related solutions.

7. Genomics / Bioinformatics:

   • Locating regions in DNA sequences with the highest occurrence of

Interview questions

Here are some interview questions related to Kadane’s Algorithm

1. What is Kadane’s Algorithm and what problem does it solve?

Answer: Kadane’s Algorithm finds the maximum sum of a contiguous subarray in linear time.
It maintains a running sum and updates a global max at each step.

2. What is the time and space complexity of Kadane’s Algorithm?

Answer: Time complexity is O(n), and space complexity is O(1).

3. How does Kadane’s Algorithm handle arrays with all negative numbers?

Answer: It returns the least negative number since combining negatives only decreases the sum.

4. How can you modify Kadane’s Algorithm to return the actual subarray?

Answer: Track start and end indices along with current sum. Update them when a new max is found.

5. How do you apply Kadane’s Algorithm to a circular array?

Answer: Use standard Kadane for max sum. Also, compute total sum - min subarray sum (using a modified Kadane) for circular case.