Task 1: Product Subarray
Given an array of integers, find the contiguous subarray within the array that has the largest product.
Example Output
Input: (2, 5, -1, 3)
Maximum product: 10
Logic
Track both maximum and minimum products ending at the current position. When encountering a negative number, swap max and min products because multiplying by a negative number reverses their relative values.
Perl Solution
ch-1.pl
sub max_product_sublist {
my @nums = @_;
my $max_product = $nums[0];
my $min_product = $nums[0];
my $result = $nums[0];
for my $i (1 .. $#nums) {
if ($nums[$i] < 0) {
($max_product, $min_product) = ($min_product, $max_product);
}
$max_product = max($nums[$i], $nums[$i] * $max_product);
$min_product = min($nums[$i], $nums[$i] * $min_product);
$result = max($result, $max_product);
}
return $result;
}
Python Solution
ch-1.py
def max_product_sublist(nums: List[int]) -> int:
max_product = nums[0]
min_product = nums[0]
result = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0:
max_product, min_product = min_product, max_product
max_product = max(nums[i], nums[i] * max_product)
min_product = min(nums[i], nums[i] * min_product)
result = max(result, max_product)
return result
Task 2: IPv4 Partition
Given a string containing only digits, restore it by returning all possible valid IPv4 address combinations.
Example Output
Input: "25525511135"
Output:
255.255.11.135
255.255.111.35
Logic
Use nested loops (or backtracking) to divide the digit string into 4 segments. Check that each segment is a valid octet (between 0 and 255 with no leading zeroes unless it is a single digit '0').
Perl Solution
ch-2.pl
sub is_valid_octet {
my $s = shift;
return 0 <= $s && $s <= 255 && $s == int($s);
}
sub restore_ip_addresses {
my $s = shift;
my @result;
my $n = length($s);
for my $i (1 .. 3) {
for my $j ($i + 1 .. $i + 3) {
for my $k ($j + 1 .. $j + 3) {
if ($k < $n) {
my $s1 = substr($s, 0, $i);
my $s2 = substr($s, $i, $j - $i);
my $s3 = substr($s, $j, $k - $j);
my $s4 = substr($s, $k);
if (is_valid_octet($s1) && is_valid_octet($s2) && is_valid_octet($s3) && is_valid_octet($s4)) {
push @result, "$s1.$s2.$s3.$s4";
}
}
}
}
}
return @result;
}
Python Solution
ch-2.py
def is_valid_octet(s: str) -> bool:
return 0 <= int(s) <= 255 and str(int(s)) == s
def restore_ip_addresses(s: str) -> List[str]:
result = []
n = len(s)
for i in range(1, 4):
for j in range(i + 1, i + 4):
for k in range(j + 1, j + 4):
if k < n:
s1, s2, s3, s4 = s[:i], s[i:j], s[j:k], s[k:]
if is_valid_octet(s1) and is_valid_octet(s2) and is_valid_octet(s3) and is_valid_octet(s4):
result.append(f"{s1}.{s2}.{s3}.{s4}")
return result