kadane 27s algorithm

1//C++ program to find maximum contiguous subarray using dynamic programming
2
3#include <iostream>
4#include <climits>
5using namespace std;
6
7void kadane_algo(int arr[],int n){
8    if(!n) return;
9    
10    int curr = arr[0],max = arr[0];
11    for(int i=1;i<n;i++){
12        
13        //max sum of subarray ending at pos i
14        curr = curr+arr[i] > arr[i] ? curr+arr[i] : arr[i];
15        
16        //max sum of subarray ending at any pos so far
17        max = curr > max ? curr : max;
18    }
19    
20    cout<<"Max subarray sum: "<<max<<endl;
21}
22
23int main() {
24	int arr[] = {-1,-4,-6,-7,-4};
25	int n = sizeof(arr)/sizeof(int);
26	kadane_algo(arr,n);
27	return 0;
28}

1public int kadane(int[] arr){
2	int max_so_far = 0, curr_max = Integer.MIN_VALUE;
3    for(int i: arr){
4    	max_so_far += i;
5        if(max_so_far<0) max_so_far = 0;
6        if(max_so_far>curr_max) curr_max = max_so_far;
7    }
8    return curr_max;
9}

1#include <bits/stdc++.h>
2
3using namespace std;
4int max_sumarray(int arr[],int n)//calculate the max sum; it has two parts
5{
6    int max_sum;
7    int cur_sum;
8    int count=0;
9    for(int i=0;i<n;i++)
10    {
11        if(arr[i]<0)
12        {
13            count++;
14        }
15    }
16    if(count!=n)//part 1 when elements are all +ve or +ve and -ve
17    {
18        max_sum=0;
19        cur_sum=0;
20        for(int i=0;i<n;i++)
21        {
22            cur_sum=cur_sum+arr[i];
23            if(cur_sum>max_sum)
24            {
25                max_sum=cur_sum;
26            }
27            if(cur_sum<0)
28            {
29                cur_sum=0;
30            }
31        }
32    }
33    else if(count==n)//part 2 when all the elements are -ve
34    {
35        max_sum=arr[0];
36        cur_sum=arr[0];
37        for(int i=1;i<n;i++)
38        {
39            cur_sum=max(arr[i],cur_sum+arr[i]);
40            max_sum=max(cur_sum,max_sum);
41        }
42    }
43    return max_sum;
44}
45
46int main()
47{
48    int n;
49    cout<<"enter the size of the array:"<<endl;
50    cin>>n;
51    int arr[n];
52    cout<<"enter the elements of the array:"<<endl;
53    for(int i=0;i<n;i++)
54    {
55        cin>>arr[i];
56    }
57    int max_subarray_sum=max_sumarray(arr,n);
58    cout<<max_subarray_sum<<endl;
59}
60

1/*	Code by DEVANSH SINGH
2	
3    Kadane's Algorithm
4	
5    Maximum Subarray Sum
6*/
7from sys import stdin,setrecursionlimit
8setrecursionlimit(10**7)
9
10def maxSubarraySum(arr, n) :
11
12    curSum = 0
13    preSum = 0
14    maxSum = 0
15    for i in range(n) :
16
17        if(i == 0) :
18            curSum = arr[i]
19        
20        else :
21
22            curSum = max(arr[i], preSum + arr[i])
23        
24        preSum = curSum
25        maxSum = max(maxSum, curSum)
26    
27    return maxSum
28/*	Code by DEVANSH SINGH
29*/
30
31#taking inpit using fast I/O
32def takeInput() :
33	
34    n =  int(input())
35
36    if(n == 0) :
37        return list(), n
38
39    arr = list(map(int, stdin.readline().strip().split(" ")))
40
41    return arr, n
42
43
44#main
45arr, n = takeInput()
46print(maxSubarraySum(arr, n))
47/*	Code by DEVANSH SINGH
48*/
49
50/*	Code by DEVANSH SINGH
51*/
52/*	Code by DEVANSH SINGH
53*/
54

1def kadane(inputArray):
2	maxSum = float("-inf")
3	curSum = 0
4    
5	for x in inputArray:
6  		curSum = max(0, curSum + x)
7  		maxSum = max(maxSum, curSum)
8	return maxSum