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