fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long getMaximumGrossValue(vector<int> arr) {
  5.     if (arr.empty()) return 0;
  6.  
  7.     // dp0, dp1, dp2, dp3 represent the maximum sum of the array processed so far, 
  8.     // ending in Segment 0, 1, 2, and 3 respectively.
  9.     long long dp0 = 0, dp1 = 0, dp2 = 0, dp3 = 0;
  10.  
  11.     for (size_t i = 0; i < arr.size(); i++) {
  12.         long long val = arr[i];
  13.  
  14.         long long next_dp0, next_dp1, next_dp2, next_dp3;
  15.  
  16.         if (i == 0) {
  17.             // For the very first element, it forms the start of whatever segment we choose.
  18.             next_dp0 = val;
  19.             next_dp1 = -val;
  20.             next_dp2 = val;
  21.             next_dp3 = -val;
  22.         } else {
  23.             // Segment 0 (+1): Must come from Segment 0
  24.             next_dp0 = dp0 + val;
  25.  
  26.             // Segment 1 (-1): Can continue Segment 1, or transition from Segment 0
  27.             next_dp1 = max(dp0, dp1) - val;
  28.  
  29.             // Segment 2 (+1): Can continue Segment 2, or transition from 0 or 1
  30.             next_dp2 = max({dp0, dp1, dp2}) + val;
  31.  
  32.             // Segment 3 (-1): Can continue Segment 3, or transition from 0, 1, or 2
  33.             next_dp3 = max({dp0, dp1, dp2, dp3}) - val;
  34.         }
  35.  
  36.         // Update states for the next element
  37.         dp0 = next_dp0;
  38.         dp1 = next_dp1;
  39.         dp2 = next_dp2;
  40.         dp3 = next_dp3;
  41.     }
  42.  
  43.     // The maximum possible value is the best outcome across any of the valid ending states.
  44.     long long final_ans = max({dp0, dp1, dp2, dp3});
  45.  
  46.     return (long)final_ans;
  47. }
  48.  
  49. int main() {
  50.     // Example from the problem description
  51.     std::vector<int> arr = {-5, 3, 9, 4};
  52.     // vector<int> arr = {-1,1,-2,-2};
  53.     // vector<int> arr= {4,-8,2,-10,3,-20};
  54.     std::cout << "Max Gross Value: " << getMaximumGrossValue(arr) << std::endl; // Output: 21
  55.     return 0;
  56. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max Gross Value: 21
https://ideone.com/qUmU00
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!