Codility/Maximum Slice.cpp at main · MortezaKhandan/Codility · 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

#include <iostream>
#include <vector>
#include <stdio.h>
#include <stack>
#include <map>
#include <limits.h>
using namespace std;
//Kadane’s Algorithm
//https://www.enjoyalgorithms.com/blog/maximum-subarray-sum
int Max(int A, int B)
{
    return A > B ? A : B;
}
int solution(vector<int> &X)
{
    int n = X.size();
    int maxsumSoFar = X[0];
    int maxsumEndingHere = X[0];
    for (int i = 1; i < n; ++i)
    {
        maxsumEndingHere = max(maxsumEndingHere + X[i], X[i]);
        if (maxsumSoFar < maxsumEndingHere)
            maxsumSoFar = maxsumEndingHere;
    }
    return maxsumSoFar;
}
int solution_c(int X[], int n)
{
    int maxsumSoFar = X[0];
    int maxsumEndingHere = X[0];
    for (int i = 1; i < n; ++i)
    {
        maxsumEndingHere = max(maxsumEndingHere + X[i], X[i]);
        if (maxsumSoFar < maxsumEndingHere)
            maxsumSoFar = maxsumEndingHere;
    }
    return maxsumSoFar;
}

// int solution(vector<int> &A)
// {
//     int intMaxSlice = INT_MIN;
//     int intMaxEnded = 0;
//     int len = A.size();
//     for (int i = 0; i < len; ++i)
//     {
//         intMaxEnded = intMaxEnded + A[i];
//         intMaxSlice = Max(intMaxSlice, intMaxEnded);
//         intMaxEnded = Max(0, intMaxEnded);
//     }
//     return intMaxSlice;
// }

int main()
{
    // -2, 1  expected  1
    // -10    expected -10
    int a[] = {5, -7, 3, 5, -2, 4, -1, -1};
    int a1[] = {-1, -1, 1};
    // printf("%d", solution(a, sizeof(a) / sizeof(a[0])));
    std::vector<int> intVec = {5, -7, 3, 5, -2, 4, -1, -1};
    std::vector<int> intVec1 = {-1, -1, 1};
    printf("%d", solution(intVec1));
    printf("\n");
    printf("%d", solution_c(a1, sizeof(a1) / sizeof(a1[0])));
    printf("\n");
    return 0;
}