Wheel of fortune

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> C(N);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }

    if (N == 3) {
        int max_gain = 0;
        for (int i = 0; i < 3; ++i) {
            int gain = C[(i + 0) % 3] - C[(i + 1) % 3];
            max_gain = max(max_gain, gain);
        }
        cout << max_gain << endl;
        return 0;
    }

    vector<long long> dp_black(N, 0), dp_red(N, 0), dp_green(N, 0);

    dp_black[0] = C[0];
    dp_red[0] = -C[0];
    dp_green[0] = 0;

    for (int i = 1; i < N; ++i) {
        dp_black[i] = max(dp_red[i - 1], dp_green[i - 1]) + C[i];
        dp_red[i] = max(dp_black[i - 1], dp_green[i - 1]) - C[i];
        dp_green[i] = max(dp_black[i - 1], dp_red[i - 1]);
    }

    long long max_profit = max({dp_black[N - 1], dp_red[N - 1], dp_green[N - 1]});

    if (N > 2) {
        vector<long long> dp_black_with_first(N, 0), dp_red_with_first(N, 0), dp_green_with_first(N, 0);

        dp_black_with_first[0] = C[0];
        dp_red_with_first[0] = -C[0];
        dp_green_with_first[0] = 0;

        dp_black_with_first[1] = max(dp_red_with_first[0], dp_green_with_first[0]) + C[1];
        dp_red_with_first[1] = max(dp_black_with_first[0], dp_green_with_first[0]) - C[1];
        dp_green_with_first[1] = max(dp_black_with_first[0], dp_red_with_first[0]);

        for (int i = 2; i < N; ++i) {
            dp_black_with_first[i] = max(dp_red_with_first[i - 1], dp_green_with_first[i - 1]) + C[i];
            dp_red_with_first[i] = max(dp_black_with_first[i - 1], dp_green_with_first[i - 1]) - C[i];
            dp_green_with_first[i] = max(dp_black_with_first[i - 1], dp_red_with_first[i - 1]);
        }

        max_profit = max(max_profit, dp_black_with_first[N - 1]);
    }

    cout << max_profit << endl;

    return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: ACCEPTED

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: ACCEPTED

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: WRONG ANSWER

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: WRONG ANSWER

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: WRONG ANSWER

Test 62

Verdict: WRONG ANSWER

Test 63

Verdict: ACCEPTED

Test 64

Verdict: WRONG ANSWER

Test 65

Verdict: ACCEPTED

Test 66

Verdict: WRONG ANSWER

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: WRONG ANSWER

Test 71

Verdict: ACCEPTED

Test 72

Verdict: WRONG ANSWER

Test 73

Verdict: ACCEPTED

Test 74

Verdict: ACCEPTED

Test 75

Verdict: WRONG ANSWER

Test 76

Verdict: WRONG ANSWER

Test 77

Verdict: WRONG ANSWER

Test 78

Verdict: WRONG ANSWER

Test 79

Verdict: WRONG ANSWER

Test 80

Verdict: WRONG ANSWER

Test 81

Verdict: ACCEPTED

Test 82

Verdict: ACCEPTED

Test 83

Verdict: ACCEPTED

Test 84

Verdict: WRONG ANSWER

Test 85

Verdict: WRONG ANSWER

Test 86

Verdict: WRONG ANSWER

Test 87

Verdict: ACCEPTED

Test 88

Verdict: WRONG ANSWER

Test 89

Verdict: ACCEPTED

Test 90

Verdict: ACCEPTED

Test 91

Verdict: WRONG ANSWER

Test 92

Verdict: ACCEPTED

Test 93

Verdict: WRONG ANSWER

Test 94

Verdict: ACCEPTED

Test 95

Verdict: ACCEPTED

Test 96

Verdict: ACCEPTED

Test 97

Verdict: ACCEPTED

Test 98

Verdict: ACCEPTED

Test 99

Verdict: ACCEPTED

Test 100

Verdict: ACCEPTED