Get this book -> Problems on Array: For Interviews and Competitive Programming

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], [3], [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 :**

- A string is always denoted by a "" (double quotes) and a character is denoted by ''(single quotes).
- 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 :**

- Contiguous subsequence is same as a subarray and a substring.
- Subsequence can be in context of both arrays and strings.
- 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;
class Kadane_Algo{
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;
class Kadane_Algo{
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;
class Kadane_Algo{
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).

## Quick Review

#### Question 1

#### Find the maximum sum of the subarray int[] a = {-2, -3, 0, -1, -2, -1, -5, -3};

#### Question 2

#### Does Kadane's Algorithm work for both positive and negative numbers !?

With this article at OpenGenus, you must have the complete idea of Kadane's Algorithm. Enjoy.