Algorithms/MaxSubarraySum.cpp at master · AnkithReddy02/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/******************REFER GFG *****************************/


#include<bits/stdc++.h>
#define MAX(a,b,c) max(a,max(b,c))
using namespace std;

int crossingsum(int a[],int low,int middle , int high)
{
    int max_left_sum = INT_MIN;

    int sum = 0;

    for(int i=middle;i>=low;i--)
    {
        sum += a[i];

        if(max_left_sum < sum)
        {
            max_left_sum =   sum;
        }
    }

    int max_right_sum = INT_MIN;

    sum = 0;

    for(int i=middle+1;i<=high;i++)
    {
        sum += a[i];

        if(max_right_sum < sum)
        {
            max_right_sum = sum;
        }
    }

    return MAX(max_left_sum + max_right_sum  ,  max_right_sum ,  max_left_sum);


}


int maxsubarraysum(int a[],int low,int high)
{
    if(low==high)
    {
        return a[low];
    }

    int middle = (low + high)/2 ;

    return MAX(maxsubarraysum(a,low,middle),maxsubarraysum(a,middle+1,high),crossingsum(a,low,middle,high));
}
int main()
{
    int n;
    cin >> n;

    int a[n];

    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }

    cout << maxsubarraysum(a,0,n-1) << endl;
}