Challenge: The Careful Collector

Lab Java Intermediate 20 points

Treasure chests stand in a row. Opening two neighbouring chests triggers a trap. What is the most gold you can collect?

Input

Line 1: n (n ≥ 1). Line 2: n amounts of gold (≥ 0).

Output

The most gold.

Example

Input

7
6 7 1 30 8 2 4

Output

Sample input available Sample output available

Editor

Java

Hints

best[i] = the most gold from chests 0..i.

Skip chest i (best[i - 1]) or open it (gold[i] + best[i - 2]). Watch out when n is 1.

Solution explanation

One pass, O(n). Each chest only needs the two answers before it.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] gold = new long[n];
        for (int i = 0; i < n; i++) gold[i] = sc.nextLong();
        long[] best = new long[n];
        best[0] = gold[0];
        if (n > 1) best[1] = Math.max(gold[0], gold[1]);
        for (int i = 2; i < n; i++) {
            best[i] = Math.max(best[i - 1], gold[i] + best[i - 2]);
        }
        System.out.println(best[n - 1]);
    }
}

Output

Answer