competitive_programming/kadane.cpp at main · costadev00/competitive_programming · 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
// C++ program to print largest contiguous array sum
#include <iostream>
#include <climits>
using namespace std;

int maxSubArraySum(int v[], int n)
{
    int best = 0, sum = 0, start = 0, end = 0, s = 0;

    // for (int i = 0; i < n; i++)
    // {
    //     sum += v[i];

    //     if (sum > best)
    //     {
    //         best = sum;
    //         start = s;
    //         end = i;
    //     }

    //     if (sum < 0)
    //     {
    //         sum = 0;
    //         s = i + 1;
    //     }
    // }
    for (int i = 0; i < n; i++)
    {
        sum = max(v[i], sum + v[i]);
        if (sum > best)
        {
            best = sum;
            start = s;
            end = i;
        }
        if (sum < 0)
        {
            sum = 0;
            s = i + 1;
        }
        // best = max(best, sum);
    }
    cout << best << "\n";
    cout << "Maximum contiguous sum is "
         << best << endl;
    cout << "Starting index " << start
         << endl
         << "Ending index " << end << endl;
}

/*Driver program to test maxSubArraySum*/
int main()
{
    int n;
    cin >> n;
    int v[n + 1];
    for (int i = 0; i < n; i++)
        cin >> v[i];
    // int n = sizeof(a) / sizeof(a[0]);
    int max_sum = maxSubArraySum(v, n);
    return 0;
}