HackerRank Sherlock and Cost problem solution

In this HackerRank Sherlock and Cost problem solution, we have given an array B and must determine an array A and we need to select a series of A[i] given B[i] such that the sum of the absolute difference of consecutive pairs of A is maximized. this will be the array’s cost and will be represented by the summation of i=2 to N by A[i] – A[i – 1].

Problem solution in Python.

# Enter your code here. Read input from STDIN. Print output to STDOUT

def solve(B):

    N = len(B)
    assert 1 <= N <= pow(10,5)
    assert all(1 <= b <= 100 for b in B)

    llen, rlen = 0, 0
    right_pos = B[0]

    for i in range(1,N):

        new_llen = rlen + (right_pos - 1)
        new_right_pos = B[i]
        new_rlen = max(
            llen + (new_right_pos - 1),
            rlen + abs(new_right_pos - right_pos))

        llen, rlen = new_llen, new_rlen
        right_pos = new_right_pos

    return max(llen, rlen)

T = int(input())

for _ in range(T):
    N = int(input())
    B = [ int(X) for X in input().split() ]
    print(solve(B))

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution 
{

    public static void main(String[] args) 
    {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        while (T > 0)
        {
            int N = scanner.nextInt();
            int length = N;
            int inputArray[] = new int[length];
            for(int i=0; i<N; i++)
            {
                inputArray[i] = scanner.nextInt();     
            }
            int dp[][] = new int[N][2];
            dp[0][0]=0;
            dp[0][1]=0;
            for(int i=1; i<N; i++)
            {
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + inputArray[i-1] - 1);
                dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + inputArray[i] -1);
            }
            System.out.println(Math.max(dp[N-1][0], dp[N-1][1]));
            T--;
        }
    }
}

Problem solution in C++.

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<climits>
using namespace std;
int main()
{
    long long num;
    cin>>num;
    for(auto i=0;i<num;++i)
    {
        long long n;
        cin>>n;
        vector<long long> v(n,0);
        for(auto j=0;j<n;++j)
            cin>>v[j];
        vector<long long> temp={0,0};
        vector<vector<long long>> dp(n,temp);
        for(auto j=1;j<n;++j)
        {
            dp[j][0]=max(dp[j-1][1]+abs(v[j]-1),dp[j-1][0]+abs(v[j]-v[j-1]));
            dp[j][1]=max(dp[j-1][0]+abs(1-v[j-1]),dp[j-1][1]);
        }
        cout<<max(dp[n-1][0],dp[n-1][1])<<endl;
    }
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
int main() {
    int T,N,B,L,R,ML,MR,X,Y,P,Q;
    scanf("%d",&T);
    for(int i = 0; i < T; i++) {
        scanf("%d",&N);
        for(int j = 0; j < N; j++) {
            scanf("%d",&B);
            if(j) {
                X = L - 1 + ML;
                Y = R - 1 + MR;
                P = abs(L - B) + ML;
                Q = abs(R - B) + MR;
                ML = (X > Y ? X : Y);
                MR = (P > Q ? P : Q);
            } else {
                ML = MR = 0;
            }
            L = 1;
            R = B;
        }
        printf("%dn", (ML > MR ? ML : MR));
    }
    return 0;
}