DSAImportantQuestionScratch/revisitingMaxCircularSum.cpp at master · saumya1singh/DSAImportantQuestionScratch · 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
#include <iostream>
using namespace std;

//Max sum in circular array
//Max of Kadane and TotalSum-(-Kadane)

int sumUsingKadane(int n, int a[]);

int sumForCircular(int n, int a[]){
    int sum= 0;
    int ans;
    for(int i=0; i<n; ++i){
        sum+=a[i];
        a[i]=-a[i];
    }
    ans=sum-(-sumUsingKadane(n,a));
    return ans;
}


int sumUsingKadane(int n, int a[]){
    int maxEndsHere=0;
    int maxSum=0;
    for(int i=0;i<n;++i){
        maxEndsHere+=a[i];
        if(maxEndsHere<0){
            maxEndsHere=0;
        }
        if(maxSum<maxEndsHere){
            maxSum=maxEndsHere;
        }
    }
    return maxSum;
}


int main() {
    int n;
    cin>>n;

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

    int sumWay1= sumUsingKadane(n,a);
    cout<<sumWay1<<endl;

    int sumWay2= sumForCircular(n,a);
    cout<<sumWay2<<endl;

    cout<<max(sumWay1,sumWay2);
}