🔥Kadane's Algorithm OR Largest sum contiguous subarray🔥

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

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