Kadane's algorithm

Kadane algorithm

public int kadane(int[] arr){
	int max_so_far = 0, curr_max = Integer.MIN_VALUE;
    for(int i: arr){
    	max_so_far += i;
        if(max_so_far<0) max_so_far = 0;
        if(max_so_far>curr_max) curr_max = max_so_far;
    }
    return curr_max;
}

Kadane's algorithm

def kadane(inputArray):
	maxSum = float("-inf")
	curSum = 0
    
	for x in inputArray:
  		curSum = max(0, curSum + x)
  		maxSum = max(maxSum, curSum)
	return maxSum

Kadane algorithm

Lets take the example:
    {-2, -3, 4, -1, -2, 1, 5, -3}

    max_so_far = max_ending_here = 0

    for i=0,  a[0] =  -2
    max_ending_here = max_ending_here + (-2)
    Set max_ending_here = 0 because max_ending_here < 0

    for i=1,  a[1] =  -3
    max_ending_here = max_ending_here + (-3)
    Set max_ending_here = 0 because max_ending_here < 0

    for i=2,  a[2] =  4
    max_ending_here = max_ending_here + (4)
    max_ending_here = 4
    max_so_far is updated to 4 because max_ending_here greater 
    than max_so_far which was 0 till now

    for i=3,  a[3] =  -1
    max_ending_here = max_ending_here + (-1)
    max_ending_here = 3

    for i=4,  a[4] =  -2
    max_ending_here = max_ending_here + (-2)
    max_ending_here = 1

    for i=5,  a[5] =  1
    max_ending_here = max_ending_here + (1)
    max_ending_here = 2

    for i=6,  a[6] =  5
    max_ending_here = max_ending_here + (5)
    max_ending_here = 7
    max_so_far is updated to 7 because max_ending_here is 
    greater than max_so_far

    for i=7,  a[7] =  -3
    max_ending_here = max_ending_here + (-3)
    max_ending_here = 4

Source: geeksforgeeks.org

Similar codes

0 vote142 views1 answer
Remove base from terminal anaconda
Python
7 votes111 views2 answers
Traceback python
Python
0 vote134 views1 answer
Dataframe move row up one
Python
0 vote109 views1 answer
Add download directory selenium python
Python
0 vote128 views1 answer
Cuantas palabras hay en una frase en python
Python
0 vote110 views1 answer
How to go sown a line in pyton
Python
1 vote166 views1 answer
Flask define template folder
Python Flask
3 votes108 views2 answers
Isalnum python
Python
0 vote190 views1 answer
Python 3 define type in arguments with default value
Python
2 votes126 views8 answers
No
Python