Answers for "Kadane's Algorithm"

2

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;
}
Posted by: Guest on June-28-2021
2

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;
}
Posted by: Guest on June-20-2020
0

kadane's algorithm

#include <bits/stdc++.h>

using namespace std;
int max_sumarray(int arr[],int n)//calculate the max sum; it has two parts
{
    int max_sum;
    int cur_sum;
    int count=0;
    for(int i=0;i<n;i++)
    {
        if(arr[i]<0)
        {
            count++;
        }
    }
    if(count!=n)//part 1 when elements are all +ve or +ve and -ve
    {
        max_sum=0;
        cur_sum=0;
        for(int i=0;i<n;i++)
        {
            cur_sum=cur_sum+arr[i];
            if(cur_sum>max_sum)
            {
                max_sum=cur_sum;
            }
            if(cur_sum<0)
            {
                cur_sum=0;
            }
        }
    }
    else if(count==n)//part 2 when all the elements are -ve
    {
        max_sum=arr[0];
        cur_sum=arr[0];
        for(int i=1;i<n;i++)
        {
            cur_sum=max(arr[i],cur_sum+arr[i]);
            max_sum=max(cur_sum,max_sum);
        }
    }
    return max_sum;
}

int main()
{
    int n;
    cout<<"enter the size of the array:"<<endl;
    cin>>n;
    int arr[n];
    cout<<"enter the elements of the array:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int max_subarray_sum=max_sumarray(arr,n);
    cout<<max_subarray_sum<<endl;
}
Posted by: Guest on June-16-2021
1

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
Posted by: Guest on May-07-2021
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
*/
Posted by: Guest on May-01-2021

Browse Popular Code Answers by Language