21 Days Training // Day (8 2/3)~(9 2/3)

T0. plant

Solution :
2 Arrays : dp1 and dp2
dp1[i] : If use i as the peak, the operations needs from the left. (Ascending)
dp2[i] : If use i as the peak, the operations needs from the right. (Descending)

ans = min(ans, max(dp1[i], dp2[i]))
Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;cin >> N;
    long long A[N];
    for (long long i=0;i<N;i++) cin >> A[i]; 
    long long dp1[N], dp2[N];
    dp1[0] = 0;
    for (int i=1;i<N;i++) dp1[i] = dp1[i-1] + (A[i-1]>=A[i]?A[i-1]-A[i]+1:0);
    dp2[N-1] = 0;
    for (int i=N-2;i>=0;i--) dp2[i] = dp2[i+1] + (A[i+1]>=A[i]?A[i+1]-A[i]+1:0);
    long long ans=LONG_LONG_MAX;
    for (int i=0;i<N;i++) ans = min(ans, max(dp1[i], dp2[i]));
    cout << ans;
}