#include <bits/stdc++.h>
using namespace std;

long getMaximumGrossValue(vector<int> arr) {
    if (arr.empty()) return 0;

    // dp0, dp1, dp2, dp3 represent the maximum sum of the array processed so far, 
    // ending in Segment 0, 1, 2, and 3 respectively.
    long long dp0 = 0, dp1 = 0, dp2 = 0, dp3 = 0;

    for (size_t i = 0; i < arr.size(); i++) {
        long long val = arr[i];
        
        long long next_dp0, next_dp1, next_dp2, next_dp3;
        
        if (i == 0) {
            // For the very first element, it forms the start of whatever segment we choose.
            next_dp0 = val;
            next_dp1 = -val;
            next_dp2 = val;
            next_dp3 = -val;
        } else {
            // Segment 0 (+1): Must come from Segment 0
            next_dp0 = dp0 + val;
            
            // Segment 1 (-1): Can continue Segment 1, or transition from Segment 0
            next_dp1 = max(dp0, dp1) - val;
            
            // Segment 2 (+1): Can continue Segment 2, or transition from 0 or 1
            next_dp2 = max({dp0, dp1, dp2}) + val;
            
            // Segment 3 (-1): Can continue Segment 3, or transition from 0, 1, or 2
            next_dp3 = max({dp0, dp1, dp2, dp3}) - val;
        }
        
        // Update states for the next element
        dp0 = next_dp0;
        dp1 = next_dp1;
        dp2 = next_dp2;
        dp3 = next_dp3;
    }

    // The maximum possible value is the best outcome across any of the valid ending states.
    long long final_ans = max({dp0, dp1, dp2, dp3});
    
    return (long)final_ans;
}

int main() {
    // Example from the problem description
    std::vector<int> arr = {-5, 3, 9, 4};
    // vector<int> arr = {-1,1,-2,-2};
    // vector<int> arr= {4,-8,2,-10,3,-20};
    std::cout << "Max Gross Value: " << getMaximumGrossValue(arr) << std::endl; // Output: 21
    return 0;
}