# Maximum subarray sum - KADANE's ALGORITHM

Mon Feb 07 2022 12:51:57 GMT+0000 (UTC)

```// Efficient Method (KADANE's ALGORITHM) : Time Complexity : O(n)

import java.util.*;
import java.io.*;

class GFG
{
static int maxSum(int arr[], int n)
{
int res = arr[0];

int maxEnding = arr[0];

for(int i = 1; i < n; i++)
{
maxEnding = Math.max(maxEnding + arr[i], arr[i]);

res = Math.max(maxEnding, res);
}

return res;
}

public static void main(String args[])
{
int arr[] = {1, -2, 3, -1, 2}, n = 5;

System.out.println(maxSum(arr, n));
}
}

// Naive : Time Complexity : O(n^2)

static int maxSum(int arr[], int n)
{
int res = arr[0];

for(int i = 0; i < n; i++)
{
int curr = 0;

for(int j = i; j < n; j++)
{
curr = curr + arr[j];

res = Math.max(res, curr);
}
}

return res;
}```
content_copyCOPY

KADANE's ALGORITHM -------------------------- maxEnding(i) = Math.max(maxEnding(i-1) + arr[i], arr[i]) Explanation: The simple idea of Kadane's algorithm is to look for all positive contiguous segments of the array ('max_ending' here is used for this). And keep track of maximum sum contiguous segment among all positive segments ('res' is used for this). Each time we get a positive-sum compare it with 'res' and update 'res' if it is greater than 'res' Lets take the example: {-2, -3, 4, -1, -2, 1, 5, -3} res = max_ending = 0 for i=0, a[0] = -2 max_ending = max_ending + (-2) Set max_ending = 0 because max_ending < 0 for i=1, a[1] = -3 max_ending = max_ending + (-3) Set max_ending = 0 because max_ending < 0 for i=2, a[2] = 4 max_ending = max_ending + (4) max_ending = 4 res is updated to 4 because max_ending greater than res which was 0 till now for i=3, a[3] = -1 max_ending = max_ending + (-1) max_ending = 3 for i=4, a[4] = -2 max_ending = max_ending + (-2) max_ending = 1 for i=5, a[5] = 1 max_ending = max_ending + (1) max_ending = 2 for i=6, a[6] = 5 max_ending = max_ending + (5) max_ending = 7 res is updated to 7 because max_ending is greater than res for i=7, a[7] = -3 max_ending = max_ending + (-3) max_ending = 4