# Kadane's Algorithm for largest subarray sum

#### Algorithms List of Mathematical Algorithms Get FREE domain for 1st year and build your brand new site

Kadane's Algorithm is commonly known for Finding the largest sum of a subarray in linear time O(N).

A Subarray of an n-element array is an array composed from a contiguous block of the original array's elements. For example, if array = [1,2,3] then the subarrays are , , , [1,2], [2,3] and [1,2,3] . Something like [1,3] would not be a subarray as it's not a contiguous subsection of the original array.

# Difference between Subarray, Substring, Subset and Subsequence

## 1. SUBARRAY

A subarray is a slice from the array which is contiguous (i.e occupy consecutive positions) and maintains the order of the elements.

NOTE : 1. If the array is of size n, then there are exactly n*(n+1)/2 subarrays that could be formed.
Also, there is no such term "contiguous/continuous subarray". So, the prefix "continuous/contiguous" is added to make the context more clear. Hence, continuous/contiguous subarray is same as subarray.

## 2. SUBSTRING

A substring of a string S is a string s' that occurs in S. Its almost similar to a subarray, but it is in context of strings.
For Example :
For String "orange" - possible subtrings are "o", "r", "a", "n", "g", "e", "or", "ora", "oran", "orang", "orange", "ra", "ran", "rang", "range", "an", "ang", "ange", "ng", "nge", "ge".

NOTE :

1. A string is always denoted by a "" (double quotes) and a character is denoted by ''(single quotes).
2. If a string is of size n, then there are exactly n*(n+1)/2 substrings that could be formed.

## 3. SUBSEQUENCE

A subsequence is a sequence that can be derived from other sequence by deleting some elements without changing the order of the remaining elements.
For Example: For array {'A','B', 'C', 'D', 'E'}, {'A', 'C', 'D'} is one of the subsequence formed after removing {B} and {E}.

So, a subarray or a substring is always contiguous but a subsequence may or maynot be contiguous. That is, unlike subarray or substring, subsequences are not required to occupy consecutive positions within the original array/string.
For Example: For array {'A','B', 'C', 'D', 'E'};
{'A', 'C', 'D'} is a subsequence but not a subarray but {'A', 'B', 'C'} is a subsequence and also a subarray.

NOTE :

1. Contiguous subsequence is same as a subarray and a substring.
2. Subsequence can be in context of both arrays and strings.
3. Generating all subsequences of an array/string is equivalent to generating power set of the array/string. For a given set S, the power set can be found by generating all binary numbers between 0 to ((2^n)-1) where n is the size of the given set.

## SUBSET

A subset is any possible combination of the original set.

A subsequence always maintain the relative order of elements of the array (i.e. increasing index) but there is no such restriction on a subset.
For Example: {3, 1} is a valid subset of {1, 2, 3, 4, 5} but it is neither a subsequence or a subarray.

All subarrays are subsequences and all subsequences are subset but the reverse is not true. For instance, the subarray {1, 2} of the array {1, 2, 3, 4, 5} is also a subsequence and a subset.

## WORKING/PSEUDO CODE OF ALGORITHM

``````Initialize:
maximum_overall = 0
maximum_ending_here = 0

Loop for each element of the array
(a) maximum_ending_here = maximum_overall + array[i]
(b) if(maximum_ending_here < 0)
maximum_ending_here = 0
(c) if(maximum_overall < maximum_ending_here)
# update needed
maximum_overall = maximum_ending_here
return maximum_overall
``````

So,
We need to look for all positive contiguous segments of the array (maximum_ending_here is used for this). And then, keep track of maximum sum contiguous segment among all positive segments (maximum_overall is used for this). Each time we get maximum_ending_here greater than maximum_overall, update maximum_overall.

EXAMPLE

So, here lets take up an example array

``````[ 3, -1, 5]
``````

The first step is to initialize the 2 variables maximum_overall and maximum_ending_here to 0.

Now, lets proceed step by step for each element given in the array :
Lets have a counter variable as i - starting from 0th index and ending at 2nd index.

When i = 0;
since maximum_overall = 0,
So, according to maximum_ending_here = maximum_overall + array[i],

``````maximum_ending_here gets updated to (0 + 3 = 3)
``````

Now, since if(maximum_ending_here < 0) is false, so it gets skipped. Next is if(maximum_overall < maximum_ending_here) condition which is true - so, maximum_overall becomes 3.

When i = 1,
since maximum_overall = 3,
So, according to maximum_ending_here = maximum_overall + array[i],

``````maximum_ending_here gets updated to (3 + (-1) = 2).
``````

Now, since if(maximum_ending_here < 0) is false, so it gets skipped. Next is if(maximum_overall < maximum_ending_here) condition which is also false - so, it gets skipped too.

Now, when i = 2,
since maximum_overall = 3,
So, according to maximum_ending_here = maximum_overall + array[i],

``````maximum_ending_here gets updated to (3 + 5 = 8)
``````

Now, since if(maximum_ending_here < 0) is false, so it gets skipped. Next is if(maximum_overall < maximum_ending_here) condition which is true - so, maximum_overall becomes 8.

Now, since i has the value of last index of our array. So, maximum_overall = 8 is returned which is our ans.

## Let's code it now!

JAVA

``````import java.util.Scanner;
public static void main (String[] args) {
int[] array = {-2, -3, 4, -1, -2, 1, 5, -3};
int size = array.length;
int maximum_overall = Integer.MIN_VALUE, max_ending_here = 0;

for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + array[i];
if (maximum_overall < max_ending_here)
maximum_overall = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
System.out.println("Maximum continuous sum of subarray is " + maximum_overall);
}
}

OUTPUT
Maximum continuous sum of subarray is 7
``````

# Some other efficient ways

So, here we do not compare for all the elements. We only compare only when max_ending_here > 0 . Though this does not reduces our Time Complexity, but it still reduces number of comparisons required.

``````import java.util.Scanner;
public static void main (String[] args) {
int[] array = {-2, -3, 4, -1, -2, 1, 5, -3};
int size = array.length;
int maximum_overall = Integer.MIN_VALUE, max_ending_here = 0;

for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + array[i];
if (max_ending_here < 0) max_ending_here = 0;
else if (maximum_overall < max_ending_here)
maximum_overall = max_ending_here;

}
System.out.println("Maximum continuous sum of subarray is " + maximum_overall);
}
}
``````

OUTPUT

``````Maximum continuous sum of subarray is 7
``````

But what would happen if all the elements in our array are negative. So, the following implementation handles this case too i.e. when all numbers in array are negative.

``````import java.util.Scanner;

public static void main(String[] args) {
int array[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int size = array.length;
int max_sum = maxSubArraySum(array, size);

for (int i = 1; i < size; i++) {
curr_max = Math.max(a[i], curr_max+a[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
System.out.println("Maximum continuous sum is " + max_so_far);
}
}
``````

OUTPUT

``````Maximum continous sum is 7
``````

Here, now instead of making comparisons using if-else if-else statements, we can directly use Math.max() function which is an inbuilt function in java used for comparing between 2 arguments and hence finding max among them.
It has no effect on time complexity but reduces our typing work.

# TIME COMPLEXITY

Time Complexity of implementing Kadane's Algorithm is O(n). This is because even for doing minimum work, we have to traverse atleast once throughout a single for loop. And for traversing a for loop, n traversals are made where n is the length of the array.

Hence, the time complexity is O(N).

-1
0
-11
2

Yes
No