🔥Kadane's Algorithm OR Largest sum contiguous subarray🔥
Tags: tutorial, todayilearned, discuss, programming
Published: 2021-03-20 08:48:09

**Question:** 

Given an array **arr** of **N** integers. Find the contiguous sub-array with maximum sum.

**Example 1:**

```
Input:
N = 5
arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.
```

**Logic:**
1. Worst complexity approach: ( O ( n ^ 3 ) ):
    - Take input as array and declare 2 variables sum = 0 and max = arr [ 0 ].
    - run 3 loops i = 0 till i  < arr.length -1, j = i+1 till j < arr.length, k = i till k ≤ j
    - in kth loop do sum += arr [ k ] and if ( sum > max ) make max = sum
    - every time you come out of the loop make sum = 0
    - and when you come out of ith loop print max
2. Better complexity approach : ( O ( n ^ 2 ) )
    - Take input as array and declare 2 variables sum = 0 and max = arr [ 0 ].
    - run 2 loops i = 0 till i  < arr.length -1, j = i+1 till j < arr.length
    - in jth loop do sum += arr [ k ] and if ( sum > max ) make max = sum
    - every time you come out of the loop make sum = 0
    - and when you come out of ith loop print max
3. Kadane's Algorithm: ( O ( n ) )
    - This algorithm is designed for such questions.
    - Take input as an array and declare two variables sum and max
    - sum = 0, max = arr [ 0 ]
    - Traverse the array and check if sum < 0 . if it is then make sum = 0
    - else sum += arr [ i ] and if sum > max then change max = sum
    - after coming out of the loop print the max

```java
import java.util.Scanner;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0; i < arr.length; i++){
            arr[i] = sc.nextInt();
        }

        //This is solution with worst time complexity of O (n^3)
        int sum = 0;
        int max = arr[0];
        for(int i = 0; i < arr.length-1; i++){
            for(int j = i+1; j < arr.length; j++){
                for(int k = i; k <= j; k++){
                    sum += arr[k];
                    if(sum > max){
                        max = sum;
                    }
                }
                sum = 0;
            }
            sum = 0;
        }
        System.out.println("Solution through worst complexity is: "+max);

        //This is solution with better time complexity of O (n^2)
        sum = 0;
        max = arr[0];
        for(int i = 0; i < arr.length-1; i++){
            for(int j = 0; j < arr.length; j++){
                sum += arr[j];
                if(sum > max){
                    max = sum;
                }
            }
            sum = 0;
        }
        System.out.println("Solution through better complexity is: "+max);

        //This is solution with best complexity. this is Kadane's algorithm O (n)
        sum = 0;
        max = arr[0];
        for(int i = 0; i < arr.length; i++){
            if(sum < 0){
                sum = 0;
            }
            sum += arr[i];
            if(sum > max){
                max = sum;
            }
        }
        System.out.println("Solution through kadane's algorithm is: "+max);
    }
}
```