Answers for "kadane's algorithm cp algorithm"

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 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;
}