dynamic programmingP0267

A rhythm game where combos build up

One song of a rhythm game has n notes, one after another. The score of the i-th note is a_i, and it may be negative. For each note you choose to hit it or let it pass. If you also hit the note right before, this note continues the combo. The first note hit in a combo earns 1 times its score, the second earns 2 times, and the third and every later note earns 3 times. Letting a note pass breaks the combo, and the next note you hit is again the first of a combo (1 times). The first note is always the first of a combo. Your total is the sum of the points earned by the notes you hit. If you hit no note, the total is 0. The first line gives n, and the second line gives a_1 … a_n separated by spaces. Print the largest total you can get.

Input: 1 ≤ n ≤ 10,000, -10,000 ≤ a_i ≤ 10,000 (integers)
Output: The largest total (an integer, 0 or more)

Example 1 · stdin

5
-1 5 3 -10 4

stdout

Example 2 · stdin

3
-5 -2 -7

stdout

main.py Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Even a negative note can be worth hitting to keep the combo so the later notes get 3 times (5 5 -1 5 5 gives 42 if you hit everything and 30 if you let only -1 pass), so the greedy idea of hitting only positive notes is wrong.
Dynamic programming that carries the best total for four states, "just let one pass / first / second / third or later in a combo", note by note finishes in n steps.
The first trap is the order of updates.
Every new value must use the previous note's values, so overwriting one at a time makes c2 use the already updated c1.
Python skip, c1, c2, c3 = …, JS/TS array destructuring [skip, c1, c2, c3] = [...] and C# tuples (skip, c1, c2, c3) = (...) update all at once.
Java, C and Craykon have no such simultaneous assignment, so compute the new values into temporaries first and then copy them.
C++ can do it with std::tie(skip, c1, c2, c3) = std::make_tuple(...), but temporaries are more common.
The second trap is the starting value of states you cannot reach yet.
Setting c1, c2, c3 to 0 before the first note pretends the first note already earns 2 or 3 times.
Start from a very small value such as Python float("-inf") or JS/TS -Infinity.
Integers in Java, C#, C and C++ have no infinity, and adding a negative score to Integer.MIN_VALUE (int.MinValue, INT_MIN) overflows: Java and C# wrap to a large positive number, and in C/C++ it is undefined behavior, so use something with room, such as half of it.
Craykon has no such constant, so write a number like -1,000,000,000,000 yourself.
Third, take the largest of all four states as the answer, which covers letting the last note pass and hitting nothing (0).

Pythonmain.py · 12 lines

n = int(input())a = list(map(int, input().split())) # 노트 하나를 지날 때마다 상태 넷의 가장 좋은 점수를 이어 간다#   skip: 이 노트를 보냈다(콤보 없음)#   c1, c2: 이 노트가 콤보의 첫째·둘째#   c3: 이 노트가 콤보의 셋째 이후(3배)NONE = float("-inf")  # 아직 닿을 수 없는 상태skip, c1, c2, c3 = 0, NONE, NONE, NONEfor x in a:    skip, c1, c2, c3 = max(skip, c1, c2, c3), skip + x, c1 + 2 * x, max(c2, c3) + 3 * xprint(max(skip, c1, c2, c3))

JavaScriptmain.js · 9 lines

const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = nums[0];// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배). -Infinity는 아직 닿을 수 없는 상태let skip = 0, c1 = -Infinity, c2 = -Infinity, c3 = -Infinity;for (let i = 1; i <= n; i++) {  const x = nums[i];  [skip, c1, c2, c3] = [Math.max(skip, c1, c2, c3), skip + x, c1 + 2 * x, Math.max(c2, c3) + 3 * x];}console.log(Math.max(skip, c1, c2, c3));

TypeScriptmain.ts · 10 lines

import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = nums[0];// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배). -Infinity는 아직 닿을 수 없는 상태let skip = 0, c1 = -Infinity, c2 = -Infinity, c3 = -Infinity;for (let i = 1; i <= n; i++) {  const x: number = nums[i];  [skip, c1, c2, c3] = [Math.max(skip, c1, c2, c3), skip + x, c1 + 2 * x, Math.max(c2, c3) + 3 * x];}console.log(Math.max(skip, c1, c2, c3));

JavaMain.java · 26 lines

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main {    // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값    static final int NONE = Integer.MIN_VALUE / 2;     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(in.readLine().trim());        StringTokenizer st = new StringTokenizer(in.readLine());        // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배)        int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE;        for (int i = 0; i < n; i++) {            int x = Integer.parseInt(st.nextToken());            int nSkip = Math.max(Math.max(skip, c1), Math.max(c2, c3));            int n1 = skip + x;            int n2 = c1 + 2 * x;            int n3 = Math.max(c2, c3) + 3 * x;            skip = nSkip; c1 = n1; c2 = n2; c3 = n3;        }        System.out.println(Math.max(Math.max(skip, c1), Math.max(c2, c3)));    }}

C#Main.cs · 21 lines

using System;using System.Linq; class Program{    // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값    const int None = int.MinValue / 2;     static void Main()    {        int n = int.Parse(Console.ReadLine());        int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();        // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배)        int skip = 0, c1 = None, c2 = None, c3 = None;        foreach (int x in a)        {            (skip, c1, c2, c3) = (Math.Max(Math.Max(skip, c1), Math.Max(c2, c3)), skip + x, c1 + 2 * x, Math.Max(c2, c3) + 3 * x);        }        Console.WriteLine(Math.Max(Math.Max(skip, c1), Math.Max(c2, c3)));    }}

C++main.cpp · 20 lines

#include <algorithm>#include <climits>#include <iostream> int main() {    // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값    const int NONE = INT_MIN / 2;    int n;    std::cin >> n;    // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배)    int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE;    for (int i = 0; i < n; i++) {        int x;        std::cin >> x;        int ns = std::max({skip, c1, c2, c3});        int n1 = skip + x, n2 = c1 + 2 * x, n3 = std::max(c2, c3) + 3 * x;        skip = ns; c1 = n1; c2 = n2; c3 = n3;    }    std::cout << std::max({skip, c1, c2, c3}) << '\n';}

Cmain.c · 23 lines

#include <limits.h>#include <stdio.h> /* 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 */#define NONE (INT_MIN / 2) static int max2(int a, int b) { return a > b ? a : b; } int main(void) {    int n;    scanf("%d", &n);    /* skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) */    int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE;    for (int i = 0; i < n; i++) {        int x;        scanf("%d", &x);        int ns = max2(max2(skip, c1), max2(c2, c3));        int n1 = skip + x, n2 = c1 + 2 * x, n3 = max2(c2, c3) + 3 * x;        skip = ns; c1 = n1; c2 = n2; c3 = n3;    }    printf("%d\n", max2(max2(skip, c1), max2(c2, c3)));    return 0;}

Craykonmain.cray · 22 lines

n = Console.ReadLine().ToNumber();a = Console.ReadNumbers();// 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작은 값못감 = -1000000000000;// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배)skip = 0;c1 = 못감;c2 = 못감;c3 = 못감;foreach (x in a){    // 새 값은 모두 이전 값으로 계산한다: 먼저 따로 구해 두고 한꺼번에 바꾼다    새skip = Mathf.Max(Mathf.Max(skip, c1), Mathf.Max(c2, c3));    새c1 = skip + x;    새c2 = c1 + 2 * x;    새c3 = Mathf.Max(c2, c3) + 3 * x;    skip = 새skip;    c1 = 새c1;    c2 = 새c2;    c3 = 새c3;}Console.WriteLine(Mathf.Max(Mathf.Max(skip, c1), Mathf.Max(c2, c3)));