---
description: A subarray is a continuous part of an array. It can be a single element of an array or some fraction of the array.
title: "Kadence’s Algorithm: Largest Sum Contiguous Subarray"
image: https://www.guru99.com/images/kadanes-algorithm.png
---

[Skip to content](#main)

**⚡ Smart Summary**

Kadane’s Algorithm finds the largest sum contiguous subarray in linear time by tracking a running maximum instead of scanning every possible subarray. This classic dynamic programming trick powers stock, finance, and signal problems.

- 🎯 **Problem Definition:** A contiguous subarray is a sequence of consecutive elements; the goal is the subarray with the highest arithmetic sum inside a mixed positive and negative array.
- 🐢 **Brute Force:** Two nested loops evaluate every start and end index in O(N²) time and print the winning window using begin and end markers.
- ⚡ **Kadane’s Insight:** Reset the running sum whenever the current element beats the accumulator, keeping only the best prefix that could still grow into the answer.
- 🧭 **Worked Example:** A short walk through of an array with negatives shows how max\_sum and current\_sum evolve step by step until the true maximum is captured.
- 💻 **Language Coverage:** Both C++ and Python implementations of the simple approach and Kadane’s Algorithm demonstrate the transition from O(N²) to O(N) time.
- 📊 **Complexity:** Kadane’s Algorithm runs in O(N) time with O(1) extra space, dramatically outperforming the brute-force baseline on large input arrays.

Read More

![Kadane's Algorithm Largest Sum Contiguous Subarray](https://www.guru99.com/images/kadanes-algorithm.png)

## What is the Largest Sum Contiguous Subarray?

A subarray is a continuous part of an array. It can be a single element of an array or some fraction of the array. The largest sum contiguous subarray means a subarray that has the maximum sum value.

For example, take the array {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Its subarrays can be {-10, 5, 1, 6}, {5, 1, 6}, or {2, -7, 3, -5}, and so on. However, {5, 1, 6, 3} cannot be a subarray because the elements are not in a contiguous sequence.

[![Largest Sum Contiguous Subarray]()](https://www.guru99.com/images/3/contiguous-subarray-1.webp)

If you notice, among all the subarrays, the highlighted subarray {5, 1, 6} has the maximum summation value:

[![Largest Sum Contiguous Subarray highlighted]()](https://www.guru99.com/images/3/contiguous-subarray-2.webp)

The sum of the subarray {5, 1, 6} is 12, the maximum sum across all possible subarrays of the above array. So, for this array, the maximum sum contiguous subarray is {5, 1, 6}.

## Simple Approach to Solving the Largest Sum Contiguous Subarray

The simple way to solve this problem is to use two loops to find all the subarrays, calculate the sum, and then find its maximum value.

Here is the flowchart for the simple approach to finding the largest sum contiguous subarray. This is a brute-force approach, as we go through every possible subarray.

[![Simple approach to Solving the Largest Sum]()](https://www.guru99.com/images/3/contiguous-subarray-3.webp)

Here are the simple steps to do this.

**Step 1)** Initialize *max\_sum* with the minimum integer value and set *begin* and *end* to zero.

**Step 2)** Let *i* and *j* be array indices where *j* is greater than or equal to *i*; *i* marks the subarray start and *j* its end.

**Step 3)** *current\_sum* holds the running sum. After each update, check if *current\_sum* is greater than *max\_sum*.

**Step 4)** If *current\_sum* is greater, replace *max\_sum* with it.

**Step 5)** When *j* reaches the end of the array, increment *i* and reset *current\_sum* to 0.

**Step 6)** Repeat until *i* reaches the end of the array. *max\_sum* then holds the largest subarray sum.

## Pseudo Code for Simple Approach

```
function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum
```

## C++ Implementation of Simple Approach

```
#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}
```

**Output:**

```
largest sum is 12
largest sum contiguous subarray: 5      1       6
```

## Python Implementation of Simple Approach

```
def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)
```

**Output:**

```
largest sum is 12
largest sum contiguous subarray: 5      1       6
```

**Don't Miss:**

- [Binary Search Algorithm with EXAMPLE](https://www.guru99.com/binary-search.html)
- [AVL Trees: Rotations, Insertion, Deletion with C++ Example](https://www.guru99.com/avl-tree.html)
- [Graph Data Structure and Algorithms (Example)](https://www.guru99.com/graphs-in-data-structures.html)
- [Bisection Method Algorithm with Examples](https://www.guru99.com/bisection-method.html)

## Kadane’s Algorithm to Find the Largest Sum Contiguous Subarray

Kadane’s Algorithm is a Dynamic Programming method that uses a single loop instead of two. It handles arrays with mixed positive and negative numbers, as long as at least one value is non-negative.

We only need two variables to find the largest sum contiguous subarray. Here is the flowchart:

[![Kadane's Algorithm to Find the Largest Sum]()](https://www.guru99.com/images/3/largest-sum-contiguous-1.webp)

Here are the steps for Kadane’s Algorithm:

**Step 1)** Create two variables, *current\_sum* and *max\_sum*.

*current\_sum* keeps the maximum sum that ends at a specific array index, while *max\_sum* stores the largest summation value observed so far.

**Step 2)** Add each array element to *current\_sum*. Then check the two conditions below:

- If *current\_sum* is less than the current element, then *current\_sum* becomes the current element.
- If *max\_sum* is less than *current\_sum*, then *max\_sum* becomes *current\_sum*.

**Step 3)** After repeating the previous step for the entire array, *max\_sum* holds the largest sum contiguous subarray.

## Example of Kadane’s Algorithm

We demonstrate Kadane’s Algorithm on a small array and walk through every step of finding the largest sum contiguous subarray.

Let us assume the given array is like the following:

[![Example of Kadane's Algorithm]()](https://www.guru99.com/images/3/contiguous-subarray-5.webp)

Here are the steps of Kadane’s Algorithm:

**Step 1)** Create two variables, *current\_sum* and *max\_sum*. Assign INT\_MIN to *max\_sum* and zero to *current\_sum*. Here, INT\_MIN represents the minimum integer value.

**Step 2)** At index 0, the value is 4. So, *current\_sum* = 0 + 4 = 4. Since *current\_sum* is larger than *max\_sum*, *max\_sum* becomes 4.

[![Example of Kadane's Algorithm step 2]()](https://www.guru99.com/images/3/contiguous-subarray-6.webp)

**Step 3)** At index 1, the value is -2. So, *current\_sum* = 4 + (-2) = 2.

This time *current\_sum* is less than *max\_sum*. As a result, the value of *max\_sum* is not updated.

[![Example of Kadane's Algorithm step 3]()](https://www.guru99.com/images/3/contiguous-subarray-7.webp)

**Step 4)** The next value is 1. Adding it to *current\_sum* gives 3. Since *max\_sum* (4) is still greater than *current\_sum*, *max\_sum* is not updated.

[![Example of Kadane's Algorithm step 4]()](https://www.guru99.com/images/3/contiguous-subarray-8.webp)

**Step 5)** At index 3, the value is 3. Incrementing *current\_sum* by 3 gives *current\_sum* = 6.

[![Example of Kadane's Algorithm step 5]()](https://www.guru99.com/images/3/contiguous-subarray-9.webp)

In this case, *max\_sum* is smaller than *current\_sum*, so *max\_sum* is updated with the value of *current\_sum*.

**Step 6)** For the last element of the array, we have -1. Adding it to *current\_sum* gives 5, which is smaller than *max\_sum*. So, *max\_sum* remains 6.

[![Example of Kadane's Algorithm step 6]()](https://www.guru99.com/images/3/contiguous-subarray-10.webp)

As we reached the end of the array, the algorithm ends here. Now, *max\_sum* contains the maximum sum, which is 6. The subarray is {4, -2, 1, 3}.

## Pseudo Code for Kadane’s Algorithm

```
function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum
```

## C++ Implementation of Kadane’s Algorithm

```
#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}
```

**Output:**

```
largest sum is 12
```

## Python Implementation of Kadane’s Algorithm

```
def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])
```

**Output:**

```
largest sum is 12
```

## Complexity Analysis for Largest Sum Contiguous Subarray

The simple approach uses two loops to calculate every possible subarray sum and locate the largest one. It is a brute-force approach; each loop runs to the end of the [array](https://www.guru99.com/array-data-structure.html), giving `O(N²)` time.

Kadane’s Algorithm uses only one loop, giving O(N) time and O(1) extra space. On an array of 100 elements the simple approach performs 100 × 100 = 10,000 operations, while Kadane’s performs only 100 — a dramatic speed-up for large inputs.

## FAQs

🤖 How is Kadane’s Algorithm used in AI and machine learning?

Kadane’s Algorithm underpins AI feature engineering for time-series data, anomaly window detection, and reward-shaping in reinforcement learning, helping models spot the strongest positive-sum interval in noisy signals.

💡 Can Copilot or GPT generate a Kadane’s Algorithm solution?

Yes. GitHub Copilot and GPT reliably output Kadane’s Algorithm in Python, C++, and Java, including variants that return the start and end indices of the winning subarray.

⏱️ What is the time complexity of Kadane’s Algorithm?

Kadane’s Algorithm runs in O(N) time and O(1) auxiliary space because it makes a single pass tracking only a running sum and a best-so-far value.

➖ How do you handle an array of all negative numbers?

Initialize max\_sum to the first element or to negative infinity instead of zero. The algorithm then returns the least-negative element, which is the correct answer.

📈 Where is the largest sum subarray useful in real problems?

Common uses are stock buy-sell profit windows, image edge sums, genomics scoring intervals, and financial risk analysis where the best contiguous return window matters most.

🔄 How do you return the actual subarray indices?

Track a temporary start index whenever current\_sum resets to the current element. When max\_sum updates, capture the start and end indices so the answer subarray can be sliced at the end.

🧩 Kadane’s vs Divide and Conquer: which is faster?

Divide and conquer solves the maximum subarray in O(N log N) by combining left, right, and crossing sums. Kadane’s Algorithm is faster at O(N) and easier to code.

🧠 Is Kadane’s Algorithm considered dynamic programming?

Yes. Kadane’s is a canonical dynamic programming example with O(1) state, where each new maximum ending at index i depends on the maximum ending at index i minus one plus the current element.

#### Summarize this post with:

ChatGPTPerplexityGrokGoogle AI

**Stay Updated on AI** **Get Weekly AI Skills, Trends, Actionable Advice.**

##### Sign up for the newsletter

Subscribe for Free

You have successfully subscribed.  
Please check your inbox.

![AI-Newsletter]() Chosen by over **350,000+** professionals

[Scroll to top](#wrapper)

×

Search for:

```json
{"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://www.guru99.com/#organization","name":"Guru99","sameAs":["https://www.facebook.com/Guru99Official","https://twitter.com/guru99com"],"logo":{"@type":"ImageObject","@id":"https://www.guru99.com/#logo","url":"https://www.guru99.com/images/guru99-logo-v1-150x59.png","contentUrl":"https://www.guru99.com/images/guru99-logo-v1-150x59.png","caption":"Guru99","inLanguage":"en-US"}},{"@type":"WebSite","@id":"https://www.guru99.com/#website","url":"https://www.guru99.com","name":"Guru99","publisher":{"@id":"https://www.guru99.com/#organization"},"inLanguage":"en-US"},{"@type":"ImageObject","@id":"https://www.guru99.com/images/kadanes-algorithm.png","url":"https://www.guru99.com/images/kadanes-algorithm.png","width":"700","height":"250","caption":"Kadane's Algorithm","inLanguage":"en-US"},{"@type":"BreadcrumbList","@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":"1","item":{"@id":"https://www.guru99.com","name":"Home"}},{"@type":"ListItem","position":"2","item":{"@id":"https://www.guru99.com/design-algorithm","name":"Algorithm"}},{"@type":"ListItem","position":"3","item":{"@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html","name":"Kadence&#8217;s Algorithm: Largest Sum Contiguous Subarray"}}]},{"@type":"WebPage","@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html#webpage","url":"https://www.guru99.com/largest-sum-contiguous-subarray.html","name":"Kadence&#8217;s Algorithm: Largest Sum Contiguous Subarray","dateModified":"2026-10-08T18:11:55+05:30","isPartOf":{"@id":"https://www.guru99.com/#website"},"primaryImageOfPage":{"@id":"https://www.guru99.com/images/kadanes-algorithm.png"},"inLanguage":"en-US","breadcrumb":{"@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html#breadcrumb"}},{"@type":"Person","@id":"https://www.guru99.com/author/editorial","name":"Editorial Team","url":"https://www.guru99.com/author/editorial","image":{"@type":"ImageObject","@id":"https://www.guru99.com/images/favicon-new-logo.png","url":"https://www.guru99.com/images/favicon-new-logo.png","caption":"Editorial Team","inLanguage":"en-US"},"sameAs":["https://www.guru99.com/editorial-team"],"worksFor":{"@id":"https://www.guru99.com/#organization"}},{"articleSection":"Algorithm","headline":"Kadence&#8217;s Algorithm: Largest Sum Contiguous Subarray","description":"A subarray is a continuous part of an array. It can be a single element of an array or some fraction of the array.","keywords":"algorithm","speakable":{"@type":"SpeakableSpecification","cssSelector":[".entry-title",".summary"]},"@type":"Article","author":{"@id":"https://www.guru99.com/author/editorial","name":"Editorial Team"},"dateModified":"2026-10-08T18:11:55+05:30","image":{"@id":"https://www.guru99.com/images/kadanes-algorithm.png"},"copyrightYear":"2026","name":"Kadence&#8217;s Algorithm: Largest Sum Contiguous Subarray","subjectOf":[{"@type":"HowTo","name":"Kadane\u2019s Algorithm to find the largest sum contiguous subarray","description":"Kadane\u2019s Algorithm is a kind of 'Dynamic Programming' method. Here we\u2019ll use one loop instead of two loops. General implementation of Kadane\u2019s Algorithm only works for positive number arrays.","step":[{"@type":"HowToStep","name":"Step 1) Create two variables, current_sum, and max_sum.","text":"'Current_sum' will keep the value of the maximum sum that ends in a specific array index, while 'max_sum' will store the maximum summation value so far.","url":"https://www.guru99.com/largest-sum-contiguous-subarray.html#step1"},{"@type":"HowToStep","name":"Step 2) We will add the value with the current_sum for each array element. Then we\u2019ll check two conditions below:","text":"If current_sum is less than the current element, then the current_sum value will be the current element.If max_sum is less than current_sum, then max_sum will be current_sum.","url":"https://www.guru99.com/largest-sum-contiguous-subarray.html#step2"},{"@type":"HowToStep","name":"Step 3) Performing the previous step for the entire array,","text":"we will have the largest sum contiguous subarray in the 'max_sum' variable.","url":"https://www.guru99.com/largest-sum-contiguous-subarray.html#step3"}]},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"How is Kadane's Algorithm used in AI and machine learning?","acceptedAnswer":{"@type":"Answer","text":"Kadane's Algorithm underpins AI feature engineering for time-series data, quick anomaly window detection, and reward-shaping in reinforcement learning. It is also used inside recommendation and forecasting pipelines to spot the strongest positive-sum interval in noisy signals."}},{"@type":"Question","name":"Can Copilot or GPT generate a Kadane's Algorithm solution?","acceptedAnswer":{"@type":"Answer","text":"Yes. AI coding assistants like GitHub Copilot and GPT reliably output Kadane's Algorithm in Python, C++, and Java, including variants that also return the start and end indices of the winning subarray."}},{"@type":"Question","name":"What is the time complexity of Kadane's Algorithm?","acceptedAnswer":{"@type":"Answer","text":"Kadane's Algorithm runs in O(N) time and uses O(1) auxiliary space because it makes a single pass through the array while tracking only a running sum and a best-so-far value."}},{"@type":"Question","name":"How do you handle an array of all negative numbers?","acceptedAnswer":{"@type":"Answer","text":"Initialize max_sum to the first element or to negative infinity instead of zero. The algorithm then returns the least-negative element, which is the correct largest sum contiguous subarray when every element is negative."}},{"@type":"Question","name":"Where is the largest sum subarray useful in real problems?","acceptedAnswer":{"@type":"Answer","text":"Common uses are stock buy-sell profit windows, image processing edge sums, genomics scoring intervals, weather trend detection, and financial risk analysis where the best contiguous return window matters most."}},{"@type":"Question","name":"How do you return the actual subarray indices?","acceptedAnswer":{"@type":"Answer","text":"Track a temporary start index whenever current_sum resets to the current element. When max_sum updates, capture the start and end indices in dedicated variables so the answer subarray can be sliced from the input array at the end."}},{"@type":"Question","name":"Kadane's vs Divide and Conquer: which is faster?","acceptedAnswer":{"@type":"Answer","text":"Divide and conquer solves the maximum subarray problem in O(N log N) time by combining left, right, and crossing sums. Kadane's Algorithm is faster at O(N) time and easier to code, so it is the standard choice in interviews."}},{"@type":"Question","name":"Is Kadane's Algorithm considered dynamic programming?","acceptedAnswer":{"@type":"Answer","text":"Yes. Kadane's Algorithm is a canonical example of dynamic programming with O(1) state, where each new maximum ending at index i depends on the maximum ending at index i minus one plus the current element."}}]}],"@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html#schema-181686","isPartOf":{"@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html#webpage"},"publisher":{"@id":"https://www.guru99.com/#organization"},"inLanguage":"en-US","mainEntityOfPage":{"@id":"https://www.guru99.com/largest-sum-contiguous-subarray.html#webpage"}}]}
```