algorithms/coderun/0404.php at master · crystarm/algorithms · GitHub

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
<?php

// longest increasing subsequence + greedy approach fail

ini_set("memory_limit", "256M");

function readInput()
{
    $input = "";
    while ($line = fgets(STDIN)) {
        $input .= $line . " ";
    }
    return preg_split("/\s+/", trim($input));
}

$tokens = readInput();

if (count($tokens) < 1) {
    exit(0);
}

$n = (int) $tokens[0];
$books = [];

for ($i = 0; $i < $n; $i++) {
    if (isset($tokens[$i + 1])) {
        $books[] = (int) $tokens[$i + 1];
    }
}

$memo = [];

function solve($idx, $left, $right)
{
    global $books, $n, $memo;

    if ($idx == $n) {
        return 0;
    }

    if (isset($memo[$idx][$left][$right])) {
        return $memo[$idx][$left][$right];
    }

    $currentH = $books[$idx];
    $res = solve($idx + 1, $left, $right);

    if ($currentH >= $left && $currentH <= $right) {
        $takeLeft = 1 + solve($idx + 1, $currentH, $right);
        $takeRight = 1 + solve($idx + 1, $left, $currentH);

        if ($takeLeft > $res) {
            $res = $takeLeft;
        }
        if ($takeRight > $res) {
            $res = $takeRight;
        }
    }

    $memo[$idx][$left][$right] = $res;
    return $res;
}

echo solve(0, 0, 101);