Kadane's Algorithm
//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;
}
4.11
9
#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;
}
Thank you!
9
0
3.5
2
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;
}
Thank you!
2
0
4
5
/* 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
*/
Thank you!
5
0
4
7
def kadane(inputArray):
maxSum = float("-inf")
curSum = 0
for x in inputArray:
curSum = max(0, curSum + x)
maxSum = max(maxSum, curSum)
return maxSum
Thank you!
7
0
Are there any code examples left?
New code examples in category Other