If the question is to convert all 0 array to target array by adding any integer x, we can use coordinate compression on target array.

And then answer is summation of max(a[i] — a[i-1],0) for all i assuming a[-1] = 0

Is it always possible to convert array $$$A$$$ into $$$B$$$ with only positive $$$K$$$?

Anyway, when there is no restriction on $$$K$$$, I think it can be solved in this way assuming $$$C_i = B_i - A_i$$$:

int fun(int l,int r,int x)
{
    int p=rmq(l,r);              // p = position of the minimum value in the subarray c[l...r]
    int o=(c[p]>0 && x<c[p]);    // if c[p] is not zero and greater than the previous minimum, count 1
    if(l<p) o+=fun(l,p-1,c[p]);  // call on the left side
    if(r>p) o+=fun(p+1,r,c[p]);  // call on the right side
    return o;                    // return the answer
}

Final answer: fun(0,n-1,c[rmq(0,n-1)]-1)

Please tell me if you have a counter case for this approach.

I think I have a solution for positive K. (EDIT2: As clyring pointed out, this solution is wrong. )

Let C[i] be B[i] — A[i]. In other words, C[i] shows us how much we need to increase A[i]. If there is an index i such that C[i] < 0, then there is no solution. Otherwise, let’s maintain a set. For every index i, this set will store the numbers by which we can increase A[i] without using a new operation. We firstly add 0 to this set. Say that the variable storing our answer is ans (initialised to 0). For every i from 1 to n, if C[i-1] < C[i] (we suppose C[0] is 0), we increment ans, else, we remove from the set all the numbers that are strictly bigger than C[i] and if we don’t find the value C[i] in the set, we increment ans. At every step, we add to the set C[i] — every value currently in the set.

For variation 2 of the problem, I don't have a solution handy, but here is some insight:

Suppose for convenience that the arrays $$$A$$$ and $$$B$$$ naturally have indices from $$$1$$$ to $$$N$$$, and that they have been extended to have $$$A[0] = B[0] = A[N+1] = B[N+1] = 0$$$. I claim that for any $$$k \in \mathbb{Z}, 0 \leq k \leq N$$$, there exists a solution with $$$k$$$ operations if and only if the multiset $$$S = \{ (B[i] - A[i]) - (B[i-1] - A[i-1]) : i \in \mathbb{Z},\, 1 \leq i \leq N+1 \}$$$ can be partitioned into $$$N+1-k$$$ nonempty multisets each with sum zero.

To see this, note that adding $$$x$$$ to every position from $$$L$$$ to $$$R$$$ in the original problem basis amounts to adding $$$x$$$ in position $$$L$$$ and $$$-x$$$ in position $$$R+1$$$ in a backwards-differences basis. Thus, for any sequence of $$$k$$$ operations that transforms $$$A$$$ into $$$B$$$, if we consider the graph $$$G$$$ with vertices numbered $$$1$$$ to $$$N+1$$$ and with an edge between $$$L$$$ and $$$R+1$$$ for every operation used, the sum

must be equal to $$$0$$$ for every connected component $$$C$$$ of the graph $$$G$$$. These connected components thus give us a partition of $$$S$$$ into at least $$$N - 1 - E$$$ nonempty multisets with sum zero, where $$$E$$$ is the number of edges, which is at most the number of operations $$$k$$$. We can then merge a few of these if $$$E < k$$$ to get exactly $$$N + 1 - k$$$ multisets.

In the reverse direction, given a partition of $$$S$$$ into $$$N + 1 - k$$$ nonempty multisets each with sum zero, we can select $$$k$$$ edges between pairs of numbers between $$$1$$$ and $$$N+1$$$ to give us a graph with connected components corresponding to this partition, and after a little bit of fairly simple linear algebra there will be a unique selection of integer weights $$$x$$$ for the operations on the $$$k$$$ intervals corresponding to these edges that will transform $$$A$$$ into $$$B$$$.

EDIT: A similar idea works for variation 1 of the problem, but with partitions of $$$\mathbb{Z} \cap [1, N+1]$$$ into nonempty sets $$$S$$$ such that the following sum is $$$0$$$ for $$$j = \max S$$$ and non-negative for all other $$$j \in S$$$:

The argument is more or less the same.

We can find the subarray indexes [l,r] first having different values in a and b using variable sliding window. After finding the subarray indexes [l,r] we can calculate the difference of b[l,r] from a[l,r] and store in a seperate array c. After that we have to do computation until all elements in array c becomes 0 and increase the counter for each computation by 1. The computation is that we have to find the min element in the array greater than 0 and put the values of (c[i]-min element) in the array c in respective indexes. The time complexity will be O(n^3). It will work with both k>0 and k<0.

#include<bits/stdc++.h>
using namespace std;
int diff_arr(vector<int> diff)
{
    int flag=0;
    for(int i=0;i<diff.size();i++)
    {
        if(diff[i]!=0)
        {
            flag=1;
            break;
        }
    }
    return flag;
}
int main()
{
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
    int i,c=0,cnt=0;
    for(i=0;i<n;i++)
    {
        if(a[i]!=b[i])
        {
            c++;
        }
        else if(a[i]==b[i] && c!=0)
        {
            vector<int> diff;
            for(int j=i-c;j<i;j++)
            {
                diff.push_back(b[j]-a[j]);
            }
            while(diff_arr(diff)!=0)
            {
                int mn=1e9+7;;
                for(int j=0;j<diff.size();j++)
                {
                    if(diff[j]!=0)
                    {
                        mn=min(mn,diff[j]);   
                    }
                }
                for(int j=0;j<diff.size();j++)
                {
                    if(diff[j]!=0)
                    {
                        diff[j]-=mn;   
                    }
                }
                cnt=cnt+1;
            }
            c=0;
        }
    }
    if(c!=0)
    {
        vector<int> diff;
        for(int j=i-c;j<i;j++)
        {
            diff.push_back(b[j]-a[j]);
        }
        while(diff_arr(diff)!=0)
        {
            int mn=1e9+7;;
            for(int j=0;j<diff.size();j++)
            {
                if(diff[j]!=0)
                {
                    mn=min(mn,diff[j]);   
                }
            }
            for(int j=0;j<diff.size();j++)
            {
                if(diff[j]!=0)
                {
                    diff[j]-=mn;   
                }
            }
            cnt=cnt+1;
        }
    }
    cout<<cnt<<endl;
    return 0;
}