1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <vector>
#include <cmath>

class Solution {
public:
    int maximumSum(std::vector<int>& arr) {
        int n = arr.size();
        std::vector<std::pair<int, int>> dp(n);
        dp[0] = {arr[0], arr[0]};
        
        int max_sum = arr[0];
        for (int i = 1; i < n; ++i) {
            dp[i].first = std::max(0, dp[i - 1].first) + arr[i];
            dp[i].second = std::max(0, dp[i - 1].second) + arr[i];
            dp[i].second = std::max(dp[i - 1].first, dp[i].second);
            max_sum = std::max(max_sum, dp[i].second);
        }
        
        return max_sum;
    }
};