← Back to DSA Course | Chapter 2: Arrays | Lesson 7 of 8

Kadane का Algorithm

Kadane का algorithm ups और downs की एक hill पर एक running total के साथ चलने जैसा है, इसे जब भी negative हो जाए drop करते हुए, ताकि आप एक walk में सबसे अच्छी stretch ढूंढ लें।

In this page:

  1. Kadane's Idea
  2. Running Sum
  3. Maximum Subarray Details
  4. Circular Array
  5. Kadane's Practice
Syntax
markup 
current = best = arr[0]
for x in arr[1:]:
    current = max(x, current + x)
    best = max(best, current)

Kadane's Idea

Kadane का algorithm किसी भी contiguous subarray का maximum possible sum एक single linear O(n) pass में ढूंढता है, जो हर possible subarray सीधे जांचने वाले O(n²) या O(n³) approaches से नाटकीय रूप से तेज़ है।

उदाहरण: Kadane's Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 9; i++) {
        curSum = max(arr[i], curSum + arr[i]);
        maxSum = max(maxSum, curSum);
    }
    cout << "Max subarray sum: " << maxSum << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = arr[0], curSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            curSum = Math.max(arr[i], curSum + arr[i]);
            maxSum = Math.max(maxSum, curSum);
        }
        System.out.println("Max subarray sum: " + maxSum);
    }
}
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = cur_sum = arr[0]
for x in arr[1:]:
    cur_sum = max(x, cur_sum + x)
    max_sum = max(max_sum, cur_sum)
print("Max subarray sum:", max_sum)
#include <stdio.h>
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 9; i++) {
        curSum = curSum + arr[i] > arr[i] ? curSum + arr[i] : arr[i];
        if (curSum > maxSum) maxSum = curSum;
    }
    printf("Max subarray sum: %d\n", maxSum);
    return 0;
}

Running Sum

यह एक running current sum रखकर काम करता है: हर element पर, यह decide करें कि पिछले subarray को extend करना अब भी current element पर एक fresh subarray शुरू करने से बेहतर है या नहीं, जो भी running sum बड़ा हो उसे अब तक देखा गया best answer रखते हुए।

उदाहरण: Running Sum

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, -1, 3, -4, 5};
    int curSum = 0, best = arr[0];
    for (int i = 0; i < 5; i++) {
        curSum = (curSum > 0) ? curSum + arr[i] : arr[i];
        cout << "After index " << i << ": running sum = " << curSum << endl;
        best = max(best, curSum);
    }
    cout << "Best: " << best << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, -1, 3, -4, 5};
        int curSum = 0, best = arr[0];
        for (int i = 0; i < arr.length; i++) {
            curSum = (curSum > 0) ? curSum + arr[i] : arr[i];
            System.out.println("After index " + i + ": running sum = " + curSum);
            best = Math.max(best, curSum);
        }
        System.out.println("Best: " + best);
    }
}
arr = [2, -1, 3, -4, 5]
cur_sum, best = 0, arr[0]
for i, x in enumerate(arr):
    cur_sum = cur_sum + x if cur_sum > 0 else x
    print(f"After index {i}: running sum = {cur_sum}")
    best = max(best, cur_sum)
print("Best:", best)
#include <stdio.h>
int main() {
    int arr[] = {2, -1, 3, -4, 5};
    int curSum = 0, best = arr[0];
    for (int i = 0; i < 5; i++) {
        curSum = (curSum > 0) ? curSum + arr[i] : arr[i];
        printf("After index %d: running sum = %d\n", i, curSum);
        if (curSum > best) best = curSum;
    }
    printf("Best: %d\n", best);
    return 0;
}

Maximum Subarray Details

सिर्फ maximum value से आगे, Kadane के algorithm को उस best subarray के exact start और end indexes track करने के लिए extend किया जा सकता है, जो तब उपयोगी है जब आपको सिर्फ sum नहीं बल्कि यह report करना हो कि कौन से elements ने इसे produce किया।

उदाहरण: Maximum Subarray Details

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0], start = 0, bestStart = 0, bestEnd = 0;
    for (int i = 1; i < 9; i++) {
        if (curSum < 0) { curSum = arr[i]; start = i; } else curSum += arr[i];
        if (curSum > maxSum) { maxSum = curSum; bestStart = start; bestEnd = i; }
    }
    cout << "Sum: " << maxSum << " from index " << bestStart << " to " << bestEnd << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = arr[0], curSum = arr[0], start = 0, bestStart = 0, bestEnd = 0;
        for (int i = 1; i < arr.length; i++) {
            if (curSum < 0) { curSum = arr[i]; start = i; } else curSum += arr[i];
            if (curSum > maxSum) { maxSum = curSum; bestStart = start; bestEnd = i; }
        }
        System.out.println("Sum: " + maxSum + " from index " + bestStart + " to " + bestEnd);
    }
}
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = cur_sum = arr[0]
start = best_start = best_end = 0
for i in range(1, len(arr)):
    if cur_sum < 0:
        cur_sum, start = arr[i], i
    else:
        cur_sum += arr[i]
    if cur_sum > max_sum:
        max_sum, best_start, best_end = cur_sum, start, i
print(f"Sum: {max_sum} from index {best_start} to {best_end}")
#include <stdio.h>
int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = arr[0], curSum = arr[0], start = 0, bestStart = 0, bestEnd = 0;
    for (int i = 1; i < 9; i++) {
        if (curSum < 0) { curSum = arr[i]; start = i; } else curSum += arr[i];
        if (curSum > maxSum) { maxSum = curSum; bestStart = start; bestEnd = i; }
    }
    printf("Sum: %d from index %d to %d\n", maxSum, bestStart, bestEnd);
    return 0;
}

Circular Array

एक circular array के लिए, जहां subarray को आखिर से वापस शुरुआत तक wrap around होने दिया जाता है, maximum circular sum पूरे array sum माइनस minimum subarray sum के बराबर है (Kadane के ज़रिए उसी तरह ढूंढा गया, बस maximize करने के बजाय minimize करते हुए)।

उदाहरण: Circular Array

#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, -3, 5};
    int total = 0, maxSum = arr[0], curMax = arr[0], minSum = arr[0], curMin = arr[0];
    for (int i = 0; i < 3; i++) {
        total += arr[i];
        curMax = max(arr[i], curMax + arr[i]); maxSum = max(maxSum, curMax);
        curMin = min(arr[i], curMin + arr[i]); minSum = min(minSum, curMin);
    }
    int maxCircular = (maxSum < 0) ? maxSum : max(maxSum, total - minSum);
    cout << "Max circular sum: " << maxCircular << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {5, -3, 5};
        int total = 0, maxSum = arr[0], curMax = arr[0], minSum = arr[0], curMin = arr[0];
        for (int x : arr) {
            total += x;
            curMax = Math.max(x, curMax + x); maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(x, curMin + x); minSum = Math.min(minSum, curMin);
        }
        int maxCircular = (maxSum < 0) ? maxSum : Math.max(maxSum, total - minSum);
        System.out.println("Max circular sum: " + maxCircular);
    }
}
arr = [5, -3, 5]
total, cur_max, max_sum, cur_min, min_sum = 0, arr[0], arr[0], arr[0], arr[0]
for x in arr:
    total += x
    cur_max = max(x, cur_max + x); max_sum = max(max_sum, cur_max)
    cur_min = min(x, cur_min + x); min_sum = min(min_sum, cur_min)
max_circular = max_sum if max_sum < 0 else max(max_sum, total - min_sum)
print("Max circular sum:", max_circular)
#include <stdio.h>
int main() {
    int arr[] = {5, -3, 5};
    int total = 0, maxSum = arr[0], curMax = arr[0], minSum = arr[0], curMin = arr[0];
    for (int i = 0; i < 3; i++) {
        total += arr[i];
        curMax = (arr[i] > curMax + arr[i]) ? arr[i] : curMax + arr[i]; if (curMax > maxSum) maxSum = curMax;
        curMin = (arr[i] < curMin + arr[i]) ? arr[i] : curMin + arr[i]; if (curMin < minSum) minSum = curMin;
    }
    int maxCircular = (maxSum < 0) ? maxSum : (maxSum > total - minSum ? maxSum : total - minSum);
    printf("Max circular sum: %d\n", maxCircular);
    return 0;
}

Kadane's Practice

Kadane का algorithm कई 'maximum subarray'-style interview problems के पीछे है, लेकिन edge cases को carefully देखें, खासकर पूरी तरह negative arrays, जहां best answer बस सबसे बड़ा (least negative) single element है।

उदाहरण: Kadane's Practice

#include <iostream>
using namespace std;
int main() {
    int arr[] = {-8, -3, -6, -2, -5, -4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 6; i++) {
        curSum = max(arr[i], curSum + arr[i]);
        maxSum = max(maxSum, curSum);
    }
    cout << "All-negative array best subarray sum: " << maxSum << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {-8, -3, -6, -2, -5, -4};
        int maxSum = arr[0], curSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            curSum = Math.max(arr[i], curSum + arr[i]);
            maxSum = Math.max(maxSum, curSum);
        }
        System.out.println("All-negative array best subarray sum: " + maxSum);
    }
}
arr = [-8, -3, -6, -2, -5, -4]
max_sum = cur_sum = arr[0]
for x in arr[1:]:
    cur_sum = max(x, cur_sum + x)
    max_sum = max(max_sum, cur_sum)
print("All-negative array best subarray sum:", max_sum)
#include <stdio.h>
int main() {
    int arr[] = {-8, -3, -6, -2, -5, -4};
    int maxSum = arr[0], curSum = arr[0];
    for (int i = 1; i < 6; i++) {
        curSum = (arr[i] > curSum + arr[i]) ? arr[i] : curSum + arr[i];
        if (curSum > maxSum) maxSum = curSum;
    }
    printf("All-negative array best subarray sum: %d\n", maxSum);
    return 0;
}
Related Topics

KMP Algorithm क्या है · Rabin-Karp Algorithm क्या है · Prefix Sum क्या है · Dutch National Flag समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. best को 0 initialize करना, इसलिए एक all-negative array गलती से 0 return करता है बजाय सबसे बड़े negative number के।
  2. Running sum को zero से नीचे गिरने पर reset न करना (या max(x, cur + x) उपयोग न करना), इसलिए bad prefixes sum को नीचे खींच लेते हैं।
  3. Running sum update करने से पहले best sum update करना, इसलिए एक value miss हो जाती है या देर से count होती है।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Prefix Sum Next Lesson → Dutch National Flag

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.