Snippets Collections
// 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;
    }
star

Mon Feb 07 2022 12:51:57 GMT+0000 (UTC) https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1/?track=DSASP-Arrays&batchId=190#

#java #gfg #geeksforgeeks #lecture #arrays #maximumsubarraysum #subarray #kadane

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension