fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. Question:
  6. You are given an integer array nums of length n, where nums[i] represents
  7. the detection value of station i.
  8.  
  9. You may choose any subset of indices to activate. If you activate no stations,
  10. the total value is 0.
  11.  
  12. If the chosen indices are:
  13. i1 < i2 < ... < ik
  14.  
  15. then the net monitoring value is:
  16.  
  17. nums[i1] + nums[i2] + ... + nums[ik]
  18. - ((i2 - i1 - 1) + (i3 - i2 - 1) + ... + (ik - i(k-1) - 1))
  19.  
  20. In other words:
  21. - each chosen station adds its value
  22. - for every pair of consecutive chosen stations, subtract the number of
  23.   unchosen indices between them
  24.  
  25. Return the maximum possible net monitoring value.
  26.  
  27. Example 1:
  28. Input: nums = [5, -2, 4]
  29. Output: 8
  30. Explanation:
  31. Choose indices [0, 2]
  32. Gain = 5 + 4 = 9
  33. Gap penalty = 2 - 0 - 1 = 1
  34. Total = 8
  35.  
  36. Example 2:
  37. Input: nums = [-3, -1, -7]
  38. Output: 0
  39. Explanation:
  40. It is better to choose no station, so the answer is 0.
  41.  
  42. Example 3:
  43. Input: nums = [3, 1, 2, 5]
  44. Output: 11
  45. Explanation:
  46. Choose all indices [0, 1, 2, 3]
  47. There are no gaps, so no penalty is paid.
  48. Total = 11
  49.  
  50. Constraints:
  51. 1 <= n <= 2 * 10^5
  52. -10^9 <= nums[i] <= 10^9
  53. */
  54.  
  55. class Solution {
  56. public:
  57.     long long maxMonitoringValue(vector<int>& nums) {
  58.         // ans = best overall answer
  59.         // Start with 0 because choosing no station is allowed
  60.         long long ans = 0;
  61.  
  62.         // best stores max(dp[j] + j) over all previous j
  63.         // where dp[j] = best value of a non-empty chosen set
  64.         // ending exactly at index j
  65.         long long best = LLONG_MIN;
  66.  
  67.         for (int i = 0; i < (int)nums.size(); i++) {
  68.             // Case 1:
  69.             // Start a new chosen set using only index i
  70.             long long cur = nums[i];
  71.  
  72.             // Case 2:
  73.             // Extend a previous set ending at j, then choose i
  74.             //
  75.             // Transition:
  76.             // dp[i] = dp[j] + nums[i] - (i - j - 1)
  77.             //       = dp[j] + nums[i] - i + j + 1
  78.             //       = (dp[j] + j) + (nums[i] - i + 1)
  79.             //
  80.             // So if we maintain max(dp[j] + j), transition becomes O(1)
  81.             if (best != LLONG_MIN) {
  82.                 cur = max(cur, best + 1LL * nums[i] - i + 1);
  83.             }
  84.  
  85.             // Update final answer
  86.             ans = max(ans, cur);
  87.  
  88.             // This index i can be the previous endpoint for future positions
  89.             best = max(best, cur + i);
  90.         }
  91.  
  92.         return ans;
  93.     }
  94. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/vfXosc
language:
C++14 (gcc 8.3)
created:
4 days 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!