Answers for "how does kadane's algorithm work"

kadane's algorithm gfg

//C++ program to find maximum contiguous subarray using dynamic programming

#include <iostream>
#include <climits>
using namespace std;

void kadane_algo(int arr[],int n){
    if(!n) return;
    
    int curr = arr[0],max = arr[0];
    for(int i=1;i<n;i++){
        
        //max sum of subarray ending at pos i
        curr = curr+arr[i] > arr[i] ? curr+arr[i] : arr[i];
        
        //max sum of subarray ending at any pos so far
        max = curr > max ? curr : max;
    }
    
    cout<<"Max subarray sum: "<<max<<endl;
}

int main() {
	int arr[] = {-1,-4,-6,-7,-4};
	int n = sizeof(arr)/sizeof(int);
	kadane_algo(arr,n);
	return 0;
}

Kadane's Algorithm

/*	Code by DEVANSH SINGH
	
    Kadane's Algorithm
	
    Maximum Subarray Sum
*/
from sys import stdin,setrecursionlimit
setrecursionlimit(10**7)

def maxSubarraySum(arr, n) :

    curSum = 0
    preSum = 0
    maxSum = 0
    for i in range(n) :

        if(i == 0) :
            curSum = arr[i]
        
        else :

            curSum = max(arr[i], preSum + arr[i])
        
        preSum = curSum
        maxSum = max(maxSum, curSum)
    
    return maxSum
/*	Code by DEVANSH SINGH
*/

#taking inpit using fast I/O
def takeInput() :
	
    n =  int(input())

    if(n == 0) :
        return list(), n

    arr = list(map(int, stdin.readline().strip().split(" ")))

    return arr, n


#main
arr, n = takeInput()
print(maxSubarraySum(arr, n))
/*	Code by DEVANSH SINGH
*/

/*	Code by DEVANSH SINGH
*/
/*	Code by DEVANSH SINGH
*/