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 :

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; 
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

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