# 解 Perl Weekly Challenge 087

## TASK #1 › Longest Consecutive Sequence

``````You are given an unsorted array of integers @N.

Write a script to find the longest consecutive sequence. Print 0 if none sequence
found.

Example 1:

Input: @N = (100, 4, 50, 3, 2)
Output: (2, 3, 4)

Example 2:

Input: @N = (20, 30, 10, 40, 50)
Output: 0

Example 3:

Input: @N = (20, 19, 9, 11, 10)
Output: (9, 10, 11)
``````

Raku 版寫來如下。時間複雜度為 O(n log(n))，空間為 O(1)：

``````sub longest-consecutive-sequence(@N) {
my @m = @N.sort({ \$^a <=> \$^b });

my \$seq_from = @m[0];
my \$seq_until = @m[0];
my \$longest_seq_from = @m[0];
my \$longest_seq_until = @m[0];
my \$longest_seq_length = 0;

for 1..@m.end -> \$i {
my \$n = @m[\$i];
if \$n - @m[\$i-1] == 0|1 {
\$seq_until = \$n;
my \$len = \$seq_until - \$seq_from;
if \$longest_seq_length < \$len {
\$longest_seq_from   = \$seq_from;
\$longest_seq_until  = \$seq_until;
\$longest_seq_length = \$len;
}
} else {
\$seq_from  = \$n;
\$seq_until = \$n;
}
}

return \$longest_seq_length == 0 ?? Nil !! [\$longest_seq_from...\$longest_seq_until];
}``````

## TASK #2 › Largest Rectangle

``````You are given matrix m x n with 0 and 1.

Write a script to find the largest rectangle containing only 1. Print 0 if none found.

Example 1:

Input:
[ 0 0 0 1 0 0 ]
[ 1 1 1 0 0 0 ]
[ 0 0 1 0 0 1 ]
[ 1 1 1 1 1 0 ]
[ 1 1 1 1 1 0 ]

Output:
[ 1 1 1 1 1 ]
[ 1 1 1 1 1 ]

Example 2:

Input:
[ 1 0 1 0 1 0 ]
[ 0 1 0 1 0 1 ]
[ 1 0 1 0 1 0 ]
[ 0 1 0 1 0 1 ]

Output: 0

Example 3:

Input:
[ 0 0 0 1 1 1 ]
[ 1 1 1 1 1 1 ]
[ 0 0 1 0 0 1 ]
[ 0 0 1 1 1 1 ]
[ 0 0 1 1 1 1 ]

Output:
[ 1 1 1 1 ]
[ 1 1 1 1 ]
``````

``````\$h = @matrix.elems;
\$w = @matrix[0].elems;``````

``([^\$h] X [^\$w])``

``````.combinations(2)
.grep(-> (\$p, \$q) { \$p[0] <= \$q[0] and \$p[1] <= \$q[1] })``````

``````.map(
-> (\$p, \$q) {
(\$p[0] .. \$q[0]).map(
-> \$y {
@matrix[\$y][ \$p[1] .. \$q[1] ]
})
})``````

…去掉不全為一者…

``````.grep(
-> @m {
([^@m] X [^@m[0]]).map(-> (\$y,\$x) { @m[\$y][\$x] == 1 }).all
}
)``````

…取寬高相乗最大者…

``.max(-> @m { @m.elems * @m[0].elems });``

``````sub largest-rectangle(@matrix) {

([^@matrix] X [^@matrix[0]])
.combinations(2)
.grep(
-> (\$p, \$q) {
\$p[0] <= \$q[0] and \$p[1] <= \$q[1]
})

.map(
-> (\$p, \$q) {
(\$p[0] .. \$q[0]).map(
-> \$y {
@matrix[\$y][ \$p[1] .. \$q[1] ]
})
})

.grep(
-> @m {
([^@m] X [^@m[0]]).map(-> (\$y,\$x) { @m[\$y][\$x] == 1 }).all
})

.max(
-> @m {
@m * @m[0]
})
}``````

``    @matrix[ \$p[0] .. \$q[0] ][ \$p[1] .. \$q[1] ]``