Sherlock and Cost

                            Solution in C :

In C++ :






#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stdio.h>
#include<map>
#include<ext/hash_map>
#include<ext/hash_set>
#include<set>
#include<string>
#include<assert.h>
#include<vector>
#include<time.h>
#include<queue>
#include<deque>
#include<sstream>
#include<stack>
#include<sstream>
#define MA(a,b) ((a)>(b)?(a):(b))
#define MI(a,b) ((a)<(b)?(a):(b))
#define AB(a) (-(a)<(a)?(a):-(a))
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ep 0.0000000001
#define pi 3.1415926535897932384626433832795

using namespace std;
using namespace __gnu_cxx;
const int N=1000111;
const int INF=1000000008;
int n,m,i,j,k,l,r,p;
int a[1000],b[1000];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>k;
        for (i=1;i<=k;i++) a[i]=0;
        for (i=k+1;i<=100;i++) a[i]=-INF;
        n--;
       //     for (i=1;i<=15;i++) cout<<a[i]<<" ";cout<<endl;
        while (n--)
        {
            scanf("%d",&k);
            p=-1;
            for (i=1;i<=k;i++)
            {
                p=MA(p+1,a[i]);
                b[i]=p;
            }
            p=-INF;
            for (i=100;i>=1;i--)
            {
                p=MA(p+1,a[i]);
                b[i]=MA(b[i],p);
            }
            for (j=k+1;j<=100;j++) b[j]=-INF;
            for (j=1;j<=100;j++) a[j]=b[j];
     //       for (i=1;i<=15;i++) cout<<a[i]<<" ";cout<<endl;
        }
    p=0;
    for (i=1;i<=k;i++) p=MA(p,a[i]);
    cout<<p<<endl;
    }
    return 0;
}








In Java :





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

public class Solution {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}

		int dpLow = 0;
		int dpHigh = 0;

		for (int i = 1; i < n; i++) {
			int nextLow = Math.max(dpLow, dpHigh + a[i - 1] - 1);
			int nextHigh = Math.max(dpLow + a[i] - 1,
					dpHigh + Math.abs(a[i] - a[i - 1]));
			dpLow = nextLow;
			dpHigh = nextHigh;
			// System.err.println(dpLow + " " + dpHigh);
		}
		
		out.println(Math.max(dpLow, dpHigh));
	}

	Solution() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		int t = nextInt();
		while (t-- > 0) {
			solve();
		}
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new Solution();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}








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("%d\n", (ML > MR ? ML : MR));
    }
    return 0;
}









In Python3 :





def cost(B) :
    c0,c1 = 0,0
    for i in range(1,len(B)) :
        c0,c1 = max(c0,c1+B[i-1]-1), max(c0+B[i]-1,c1+abs(B[i]-B[i-1]))
    return max(c0,c1)
    




T = int(input())

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