## DEV Community

Kaiwalya Koparkar

Posted on

# đ„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);
}
}
``````