Prize Collection#1619

Prize Collection (Editorial)

Let's number the boxes starting from the first one (the $i$ -th box contains $a_{i}$ a_i points). Let $f (i)$ denote the maximum sum of points that can be obtained by considering the boxes from the first to the $i$ -th, inclusive.

Then:

$f (1) = a_{1}$ f(1) = a_1,
$f (2) = ma x (a_{1}, a_{2})$ f(2) = max(a_1, a_2)

When computing $f (i)$ , consider two cases:

If the $i$ -th box is chosen, the neighboring $(i - 1)$ (i - 1)-th box cannot be selected. In this case, the maximum sum of points will be $f (i - 2) + a_{i}$ f(i - 2) + a_i.
if the $i$ -th box is not chosen, the maximum sum of points equals $f (i - 1)$ f(i - 1).

Thus,

f (i) = ma x (f (i - 2) + a_{i}, f (i - 1))

f(i) = max(f(i - 2) + a_i, f(i - 1))

Let's store the values of $f (i)$ in the array $r es$ . The answer to the problem will be the value $f (n) = r es [n]$ f(n) = res[n].

Example

Let us compute f(3)

If we do not open the third box, then we simply take the best result for the first two boxes: $f (2) = 6$ f(2) = 6.

If we open the third box, then we cannot open the second one (they are adjacent). Therefore, we take the optimal result for the first box and add the points from the third box:

f (1) + a_{3} = 6 + 2 = 8

f(1) + a_3 = 6 + 2 = 8

Сhoose the maximum of the two options:

f (3) = ma x (f (2), f (1) + a_{3}) = ma x (6, 8) = 8

f(3) = max(f(2), f(1) + a_3) = max(6, 8) = 8

Let us compute f(4)

If we do not open the fourth box, then the result equals $f (3) = 8$ f(3) = 8.

If we open the fourth box, then we cannot open the third one. So we take the best result for the first two boxes and add the points from the fourth box:

f (2) + a_{4} = 6 + 10 = 16

f(2) + a_4 = 6 + 10 = 16

Сhoose the maximum of the two options:

f (4) = ma x (f (3), f (2) + a_{4}) = ma x (8, 16) = 16

f(4) = max(f(3), f(2) + a_4) = max(8, 16) = 16

Exercise

Compute the values of $f (i)$ for the following input data:

Algorithm implementation

Declare the input array $a$ and the resulting array $r es$ .

#define MAX 1000001
long long a[MAX], res[MAX];

Read the input data.

scanf("%d",&n);
for (i = 1; i <= n; i++)
  scanf("%lld",&a[i]);

Compute the answer $r e s_{1}$ res_1 for one box, and $r e s_{2}$ res_2 for two boxes.

res[1] = a[1];
if (n > 1) res[2] = max(a[1],a[2]);

Compute the answers for the remaining boxes.

for (i = 3; i <= n; i++)
  res[i] = max(res[i - 2] + a[i], res[i - 1]);

Print the answer.

printf("%lld\n",res[n]);

Java implementation

import java.util.*; 

class Main 
{
  static long a[] = new long[1000001];
  static long res[] = new long[1000001];

  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    for (int i = 1; i <= n; i++)
      a[i] = con.nextInt();
    
    res[1] = a[1];
    if (n > 1) res[2] = Math.max(a[1],a[2]);

    for (int i = 3; i <= n; i++)
      res[i] = Math.max(res[i - 2] + a[i], res[i - 1]);

    System.out.println(res[n]);
    con.close();
  }
}

Java

Python implementation

Read the input data.

n = int(input())
lst = list(map(int,input().split()))

Initialize the list $d p$ .

dp = [0] * len(lst)

Compute the answer $d p_{0}$ dp_0 for one box, and $d p_{1}$ dp_1 for two boxes.

dp[0] = lst[0]
if (n > 1): dp[1] = max(lst[0], lst[1])

Compute the answers for the remaining boxes.

for i in range(2, len(lst)):
  dp[i] = max(dp[i-1], dp[i-2] + lst[i])

Print the answer.

print(dp[-1])