Classic.. just classic.  It is a mix of Greedy and DP. The naive DP is, iterate over all [1..Bi] which is O(n^3). However, deeper thought into the problem indicates: we only need to consider [1, Bi]. So then it becomes O(n)!

Lesson learnt: DP choices can be optimized!

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define MAX_V 101typedef long long LL;LL calc(vector
            
              &in){ size_t len = in.size(); vector
             
              
               > dp(len, vector
               
                (2, 0)); for (int i = 1; i < len; i++) { dp[i][0] = std::max(dp[i][0], in[i - 1] - 1 + dp[i-1][1]); dp[i][1] = std::max(dp[i][1], in[i] - 1 + dp[i - 1][0]); dp[i][1] = std::max(dp[i][1], abs(in[i - 1] - in[i]) + dp[i - 1][1]); } return std::max(dp[len - 1][0], dp[len - 1][1]);}int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector
                
                  in(n); for (int i = 0; i < n; i++) cin >> in[i]; LL ret = calc(in); cout << ret << endl; } return 0;}