Maximum subarray sum - KADANE's ALGORITHM

PHOTO EMBED

Mon Feb 07 2022 12:51:57 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #arrays #maximumsubarraysum #subarray #kadane

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

https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1/?track=DSASP-Arrays&batchId=190#