# Interview Questions

# Kadane’s Algorithm to find maximum subarray sum

- August 19, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example:

Array Maximum Sub-Array sum ----------------------- ----------------------- ---- {5, 7, 12, 0, -8, 6} {5, 7, 12} 24 {6, -2, -3, 4, -1, 10 } {6, -2, -3, 4, -1, 10 } 14 {-1, -3, 4, -7, 0, 2} {2} 2 {1, -5, 2, -1, 3} {2, -1, 3} 4

Note: If all elements are positive, then the result is sum of entire array. If all elements are -ve then result is zero.

**1. Brute-Force Method – O(n ^{3}) Time**

This method is to find all the possible sub-sequences of the array. Compute the Sum of all the sub-sequences and then find the maximum out of them.

If there are n elements, then total number of sub-sequences possible are

n + (n-1) + (n-2) + .... + 1 = O(n^2)

Computing sum of elements of a sub-sequence will take O(n) time. Hence the total time is O(n^{3}).

( Finding max of O(n^{2}) elements will take O(n^{2}) time.)

**Code:**

/** * Function will compute the maximum subarray. * * Will set the variables 'start' and 'end' to proper indeces * of the maximum subarray. */ void maxSubArray( int* arr, int n, int* start, int* end) { int sum, max = arr[0]; for (int i = 0; i < n ; i++) for (int j = i; j < n; j++) { sum = 0; for (int k = i; k <=j; k++) sum+= arr[k]; if (sum >= max) { *start = i; *end = j; } } }

**2. Improvement over Method-1 – O(n ^{2}) Time**

The above algorithm can be slightly improved to take O(n^{2}) time by changing the way we are computing sum of sub-arrays. Let arr[i .. j] represents – “sum of sub-array from position i to j“, then this algorithm uses the fact that

arr[i .. j] = arr[j] + arr[i .. j-1]

Hence, we will not compute the sum of entire sub-array every time, but reuse the sum of previously computed sub-array to get the sum of current sub-array.

/** * Improvement over the function in point-1 * * Sum of sequence arr[i .. j] = arr[j] + sum of sequence arr[i .. j-1] */ void maxSubArray(int *arr, int n, int &start, int &end) { int sum, max = arr[0]; for (int i = 0; i < n; i++) { sum = 0; for (int j = i; j < n; j++) { sum + = arr[j]; if (sum >= max) { start = i; end = j; } } } }

**3. Kadane’s Algorithm (Using Dynamic Programming) – O(n) Time**

This problem can be solved in linear time using Dynamic Programming. There are O(n) subproblems, each of which can be solved using the previously solved subproblem.

It uses two variables as shown in the algorithm at this wiki page

**Algorithm:**

// Two variables to store results max_ending_here = max_so_far = 0 for i = 0 to n-1 max_ending_here = max(a[i], max_ending_here + a[i]) max_so_far = max(max_so_far, max_ending_here) return max_so_far

**Code:**

int maxSubArraySum(int *arr, int n) { int max_so_far = 0; int max_ending_here = 0; for(int i = 0; i < n; i++) { max_ending_here = max_ending_here + arr[i]; if(max_ending_here < 0) max_ending_here = 0; if(max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far; }

**References:**

http://www.cs.cmu.edu/~15210/lectures/lecture03.pdf

http://en.wikipedia.org/wiki/Kadane%27s_Algorithm

wrong Kadane’s Algorithm

Doesnt work for [-1,-2]

Isnt in the 3rd example sub array would be {4}

Hello there, just became aware of your weblog by way of Google, and identified that it is actually informative. I’m going to watch out for brussels. I’ll be grateful in the event you continue this in future. Lots of people will probably be benefited from your writing. Cheers!