The Weekly Challenge 061

Product Subarray and IPv4 Partition

Solutions on GitHub

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