HackerRank Sherlock and Cost Problem Solution
In this post, we will solve HackerRank Sherlock and Cost Problem Solution.
[1,1,1], [1,1,2], [1,1,3]
[1,2,1], [1,2,2], [1,2,3]
Our calculations for the arrays are as follows:
|1-1| + |1-1| = 0 |1-1| + |2-1| = 1 |1-1| + |3-1| = 2
|2-1| + |1-2| = 2 |2-1| + |2-2| = 1 |2-1| + |3-2| = 2
The maximum value obtained isĀ 2.
Function Description
Complete the cost function in the editor below. It should return the maximum value that can be obtained.
cost has the following parameter(s):
- B: an array of integers
Input Format
The first line contains the integer t, the number of test cases,
Each of the next t pairs of lines is a test case where:
- The first line contains an integern, the length of B
-The next line contains n space-separated integers B[i]
Output Format
For each test case, print the maximum sum on a separate line.
Sample Input
1
5
10 1 10 1 10
Sample Output
36
Explanation
The maximum sum occurs when A[1]=A[3]=A[5]=10 and A[2]=A[4]=1. That is 1-10+10-1+1 – 10 + 10-1 = 36.
Sherlock and Cost C Solution
#include <stdio.h>
int max(int a, int b){
return (a>b)?a:b;
}
int abs(int a){
return (a>0)?a:(a*-1);
}
int main(void) {
int t,n,i;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d", &arr[i]);
int low = 0, high = 0,l,h;
for(i=1;i<n;i++){
l = max(abs(1-arr[i-1])+high, low);
h = max(abs(arr[i]-1)+low, abs(arr[i]-arr[i-1])+high);
high = h;
low = l;
}
printf("%d\n", max(low,high));
}
return 0;
}
Sherlock and Cost C++ Solution
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
template <typename S, typename T>
static S solve(const std::vector<T> &bounds) {
S top = 0;
S bottom = 0;
for (int i = 1; i < bounds.size(); ++i) {
auto q = std::max(bottom, top + (bounds[i - 1] - 1));
top = std::max(top + abs(bounds[i] - bounds[i - 1]), bottom + (bounds[i] - 1));
bottom = q;
}
return std::max(bottom, top);
}
int main() {
int testCount{};
std::cin >> testCount;
std::vector<int> bounds;
for (int k = 0; k < testCount; ++k) {
int n{};
std::cin >> n;
bounds.resize(n);
std::copy_n(std::istream_iterator<int>(std::cin), n, bounds.begin());
std::cout << ::solve<long long>(bounds) << '\n';
}
return 0;
}
Sherlock and Cost C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
int T = Convert.ToInt32(Console.ReadLine());
for (int t = 0; t < T; t++) {
int N = Convert.ToInt32(Console.ReadLine());
int[] BArray = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
int maxOne = 0;
int maxA = 0;
for (int i = 1; i < N; i++) {
int currOne = Math.Max(maxOne, maxA + BArray[i-1] - 1);
int currA = Math.Max(maxOne + BArray[i] - 1, maxA + Math.Abs(BArray[i] - BArray[i-1]));
maxOne = currOne;
maxA = currA;
}
Console.WriteLine(Math.Max(maxOne, maxA));
}
}
}
Sherlock and Cost Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'cost' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY B as parameter.
*/
public static int cost(List<Integer> B) {
// Write your code here
Integer low = 0;
Integer hi = 0;
for (var i = 1; i < B.size(); i++) {
Integer h2l = Math.abs(B.get(i-1) - 1);
Integer l2h = Math.abs(B.get(i) - 1);
Integer h2h = Math.abs(B.get(i) - B.get(i-1));
Integer lowNext = Math.max(low, hi+h2l);
Integer hiNext = Math.max(hi+h2h, low+l2h);
low = lowNext;
hi = hiNext;
}
return Math.max(low, hi);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, t).forEach(tItr -> {
try {
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> B = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.cost(B);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}
Sherlock and Cost JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding("ascii");
var input = "";
process.stdin.on("data", function (chunk) {
input += chunk;
});
process.stdin.on("end", function () {
processData(input);
});
function processData (input) {
const lines = input.split(/\n/);
const T = +lines.shift();
for (let t = 0; t < T; t++) {
const N = +lines.shift();
const a = lines.shift().split(' ').map(Number);
const b = [[0, 0]];
for (let i = 1; i < N; i++) {
b[i] = [
Math.max(b[i-1][0], b[i-1][1] + a[i-1]-1),
Math.max(b[i-1][0] + a[i]-1, b[i-1][1] + Math.abs(a[i] - a[i-1]))
];
}
console.log(Math.max(...b[N-1]));
}
}
Sherlock and Cost Python Solution
t = int(input())
for _ in range(t):
input()
bs = iter(map(int, input().split()))
last = next(bs)
cost_one = 0
cost_max = 0
for b in bs:
cost_one, cost_max = max(cost_one, cost_max + last - 1), max(cost_max + abs(last - b), cost_one + b - 1)
last = b
print(max(cost_one, cost_max))