fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4.  
  5. using namespace std;
  6.  
  7. void solve() {
  8.     int n;
  9.     cin >> n;
  10.     vector<int> a(n);
  11.  
  12.     for (int i = 0; i < n; i++) {
  13.         cin >> a[i];
  14.     }
  15.  
  16.     vector<long long> dp_no_skip(n, LONG_MIN);
  17.     vector<long long> dp_skipping(n, LONG_MIN);
  18.     vector<long long> dp_after_skip(n, LONG_MIN);
  19.  
  20.     long long max_rating = LONG_MIN;
  21.  
  22.     dp_no_skip[0] = 0;
  23.  
  24.     for (int i = 1; i < n; i++) {
  25.         if (a[i] > dp_no_skip[i-1]) {
  26.             dp_no_skip[i] = dp_no_skip[i-1] + 1;
  27.         } else if (a[i] == dp_no_skip[i-1]) {
  28.             dp_no_skip[i] = dp_no_skip[i-1];
  29.         } else {
  30.             dp_no_skip[i] = dp_no_skip[i-1] - 1;
  31.         }
  32.  
  33.         if (i >= 1) {
  34.             dp_skipping[i] = dp_no_skip[i-1];
  35.         }
  36.  
  37.         if (i >= 2) {
  38.             dp_after_skip[i] = dp_skipping[i-2];
  39.         }
  40.  
  41.         max_rating = max(max_rating, dp_skipping[i]);
  42.     }
  43.  
  44.     cout << max_rating << endl;
  45. }
  46.  
  47. int main() {
  48.     int t;
  49.     cin >> t;
  50.  
  51.     for (int i = 0; i < t; i++) {
  52.         solve();
  53.     }
  54.  
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10
stdout
copy 
4
2
-9223372036854775808
4
3
https://ideone.com/cEOZN8
language:
C++14 (gcc 8.3)
created:
5 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!