Top Down Approach for this dynamic programming problem

Question

Here is the problem-

You are given array B of size n. You have to construct array A such that 1<=A[i]<=B[i] and sum of the absolute difference of consecutive pairs of A is maximized ,that is, summation of abs(A[i]-A[i-1]) is maximised.You have to return this cost.

Example B=[1,2,3] A can be [1,2,1],[1,1,3],[1,2,3] In all these cases cost is 2 which is the maximum.

Constraints n<=10^5 ,1<=B[i]<=100

Here is my approach - Cost will be maximum when A[i]=1 or A[i]=B[i]

So I created dp[idx][flag][curr] of size [100002][2][102] where it calculates the cost till index idx. flag will be 0 or 1 representing if A[i] should be 1 or B[i] respectively. curr will be the value of A[i] depending upon flag

Here is my code

     #include<bits/stdc++.h>
using namespace std;
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long int ll;
#define mod 1000000007

 ll n;
ll dp[100002][2][101];
ll b[100005];
 ll solve(ll idx,ll flag,ll curr)
 {

     if(idx>=n)
         return 0;
     ll s1=0;
    if(dp[idx][flag][curr]!=-1)
        return dp[idx][flag][curr];
     if(idx==0)
     {
         int left=solve(idx+1,0,curr);
         int right=solve(idx+1,1,curr);
         return dp[idx][flag][curr]=max(left,right);
     }
     else
     {
         if(flag==0)
         {
             s1=abs(curr-1);
             return dp[idx][flag][curr]=s1+max(solve(idx+1,0,1),solve(idx+1,1,1));
         } 
         else
         {
             s1=abs(b[idx]-curr);
        return dp[idx][flag][curr]=s1+max(solve(idx+1,0,b[idx]),solve(idx+1,1,b[idx]));
         }
     }
 }


int main()
{
    boost
ll t;
cin>>t;
while(t--)
{ 
cin>>n;
memset(dp,-1,sizeof(dp));
ll res=0;
for(int i=0;i<n;i++)
    cin>>b[i];
ll s1=solve(0,0,1);//Starting from idx 0 flag 0 and value as 1
ll s2=solve(0,1,b[0]);//Starting from idx 0 flag 1 and value as B[0]
cout<<max(s1,s2)<<"\n";
}
}'

Is there any way to reduce states of dp or any other top down solution because my code fails if values of B[i] are large

Answer 1

You implement a recursive approach. Here, a simple iterative implementation allows to get a time efficiency of O(n) and a space efficiency of O(1) (not counting the space needed for the input array).

You correctly stated that at index i, we have two choices only, a[i]=1 (flag = 0) or a[i]=b[i] (flag = 1)

The basic idea is that, when studying what choice to make at index i, we only need to know what are the optimum sums ending at index i-1, for flag = 0 (sum0) or flag = 1 (sum1).

We don't need to explicitely calculate the array a[.].

Note: I kept long long int as in your code, but it seems that int is quite enough here.

#include    <iostream>
#include    <cstdio>
#include    <vector>
#include    <cstdlib>
#include    <algorithm>

#define mod 1000000007          // needed ???

long long int sum_diff (const std::vector<long long> &b) {
    int n = b.size();
    long long int sum0 = 0;
    long long int sum1 = 0;
    for (int i = 1; i < n; ++i) {
        long long int temp = std::max (sum0, sum1 + b[i-1] - 1);            // flag = 0: a[i] = 1
        sum1 = std::max (sum0 + b[i] - 1, sum1 + std::abs(b[i] - b[i-1]));  // flag = 1: a[i] = b[i]
        sum0 = temp;
    }
    return std::max (sum0, sum1);
 }


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    std::cin >> t;
    while(t--) { 
        int n;
        std::cin >> n;
        std::vector<long long int> b(n);
        for(int i = 0;i < n; i++) std::cin >> b[i];
        long long int s = sum_diff (b);
        std::cout << s << "\n";
    }
}

As you insist to have a top-down (recursive) aproach, I have implement both approaches in the following code. But I insist that the iterative solution is better in this case.

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <vector>
#include    <algorithm>

int sum_diff (const std::vector<int> &b) {
    int n = b.size();
    int sum0 = 0;
    int sum1 = 0;
    for (int i = 1; i < n; ++i) {
        int temp = std::max (sum0, sum1 + b[i-1] - 1);                      // flag = 0: a[i] = 1
        sum1 = std::max (sum0 + b[i] - 1, sum1 + std::abs(b[i] - b[i-1]));  // flag = 1: a[i] = b[i]
        sum0 = temp;
    }
    return std::max (sum0, sum1);
 }

 void sum_diff_recurs (const std::vector<int> &b, int i, int&sum0, int &sum1) {
    if (i == 0) {
        sum0 = sum1 = 0;
        return;
    }
    sum_diff_recurs (b, i-1, sum0, sum1);
    int temp = std::max (sum0, sum1 + b[i-1] - 1);                      // flag = 0: a[i] = 1
    sum1 = std::max (sum0 + b[i] - 1, sum1 + std::abs(b[i] - b[i-1]));  // flag = 1: a[i] = b[i]
    sum0 = temp;
 }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    std::cin >> t;
    while(t--) { 
        int n, sum0, sum1;
        std::cin >> n;
        std::vector<int> b(n);
        for(int i = 0; i < n; i++) std::cin >> b[i];
        int s = sum_diff (b);
        std::cout << s << "\n";
        sum_diff_recurs (b, n-1, sum0, sum1);
        std::cout << std::max(sum0, sum1) << "\n";
    }
}

Answer 2

Actually I found the solution using only two states idx and flag

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll n,k;
ll dp[100002][2];
ll b[100005];

ll solve(ll idx,ll flag)
{
    if(idx>=n-1)
        return 0;
    if(dp[idx][flag]!=-1)
        return dp[idx][flag];
    ll val=(flag==1)?b[idx]:1;
    ll left=solve(idx+1,0)+val-1;
    ll right=solve(idx+1,1)+abs(val-b[idx+1]);
    return (dp[idx][flag]=max(left,right));
}

int main()
{ 
ll t;
cin>>t;
while(t--)
{ 
cin>>n;
memset(dp,-1,sizeof(dp));
ll res=0;
for(int i=0;i<n;i++)
    cin>>b[i];
ll s1=solve(0,0);
ll s2=solve(0,1);
cout<<max(s1,s2)<<"\n";
}
}