SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Kadane's Algorithm Visualizer

At each value, either extend the current subarray or start fresh here, whichever is bigger. Remember the best you have seen.

Start the Kadane's Algorithm simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Start with cur = best = -2. [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  2. Starting fresh at 1 beats extending (-2 + 1 = -1).
  3. 1 is the new best.
  4. Extend: 1 + -3 = -2.
  5. Starting fresh at 4 beats extending (-2 + 4 = 2).
  6. 4 is the new best.
  7. Extend: 4 + -1 = 3.
  8. Extend: 3 + 2 = 5.
  9. 5 is the new best.
  10. Extend: 5 + 1 = 6.
  11. 6 is the new best.
  12. Extend: 6 + -5 = 1.
  13. Extend: 1 + 4 = 5.
  14. Done. The maximum subarray is [3..6] with sum 6.

Try it with your own input →

Kadane's algorithm in Java, Python, C++, C and JavaScript

int maxSubArray(int[] a) {
  int cur = a[0], best = a[0];
  for (int i = 1; i < a.length; i++) {
    cur = Math.max(a[i], cur + a[i]);
    best = Math.max(best, cur);
  }
  return best;
}
def max_sub_array(a):
    cur = best = a[0]
    for i in range(1, len(a)):
        cur = max(a[i], cur + a[i])
        best = max(best, cur)
    return best
int maxSubArray(const vector<int>& a) {
  int cur = a[0], best = a[0];
  for (int i = 1; i < (int)a.size(); i++) {
    cur = max(a[i], cur + a[i]);
    best = max(best, cur);
  }
  return best;
}
int maxSubArray(int a[], int n) {
  int cur = a[0], best = a[0];
  for (int i = 1; i < n; i++) {
    cur = a[i] > cur + a[i] ? a[i] : cur + a[i];
    if (cur > best) best = cur;
  }
  return best;
}
function maxSubArray(a) {
  let cur = a[0], best = a[0];
  for (let i = 1; i < a.length; i++) {
    cur = Math.max(a[i], cur + a[i]);
    best = Math.max(best, cur);
  }
  return best;
}

In an interview

LeetCode 53, Maximum Subarray: the contiguous subarray with the largest sum.

This is the simplest dynamic programming problem: cur is "best sum ending at i". Saying that shows you understand DP.

More patterns