Algorithm

HackerRank/Algorithm/Dynamic Programming/Sherlock and Cost

Problem Summary

Given an array B of N positive integers, and the relationship between array A and B: 1 ≤ A[i] ≤ B[i] (1 ≤ i ≤ N), find the maximum of S = sum{|A[i] - A[i-1]|}, 2 ≤ i ≤ N.

Solution

To find max S, we need to determine the values of A[i].

First, we can prove that for any i, we only need to consider 1 and B[i], i.e. A[i] = 1 or A[i] = B[i].

The rest is trivial.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib> /* abs */
#include <cmath>
using namespace std;
int main()
{
    int T,n,cur,pre,lo_hi,lo_lo,hi_lo,hi_hi,best_lo,best_hi,new_best_lo,new_best_hi;
    scanf("%d",&T);
while(T)
{
    T--;
    best_lo = best_hi = lo_hi = hi_lo = lo_lo = hi_hi = 0;
    scanf("%d",&n);
    scanf("%d",&pre);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&cur);
        lo_lo=0; /* 1 - 1 */
        lo_hi=cur-1;
        hi_lo=pre-1;
        hi_hi=abs(cur-pre);
        new_best_lo = max(best_lo,best_hi + hi_lo);
        new_best_hi = max(best_lo + lo_hi,best_hi + hi_hi);
        best_lo = new_best_lo;
        best_hi = new_best_hi;
        pre=cur;
    }
    printf("%d\n",best_lo > best_hi ? best_lo:best_hi);
}
   
    return 0;
}