Maximum L1 Distance Between Equal-Length Subarrays

Problem Statement

Given two integer arrays A and B of lengths n and m respectively, you want to choose a contiguous subarray from A and a contiguous subarray from B of the same length k >= 1 such that the L1 distance between them is maximized.

The L1 distance between subarray A[i ... i + k - 1] and subarray B[j ... j + k - 1] is defined as:

sum_{t=0}^{k-1} |A[i + t] - B[j + t]|

Write a function to return the maximum possible L1 distance between any two equal-length nonempty contiguous subarrays. Note that the result may exceed the range of a standard 32-bit signed integer.

Function Interface

def max_l1_distance(A: list[int], B: list[int]) -> int:
    pass

Inputs

• A: A list of integers representing the first array.
• B: A list of integers representing the second array.

Constraints

• 1 <= len(A), len(B) <= 2500
• -10^9 <= A[i], B[j] <= 10^9

Output

• An integer representing the maximum L1 distance achievable.

Examples

Example 1

Input: A = [1, 5, 2], B = [9, 1, 8]
Output: 15
Explanation:
Choose i = 0, j = 0, and k = 3:
|1 - 9| + |5 - 1| + |2 - 8| = 8 + 4 + 6 = 18.
Wait, let's check: |1 - 9| + |5 - 1| + |2 - 8| = 8 + 4 + 6 = 18.
If we choose i = 1, j = 0, k = 2:
|5 - 9| + |2 - 1| = 4 + 1 = 5.
The maximum possible distance is 18.

Example 2

Input: A = [10, -5], B = [2, 8, -5]
Output: 21
Explanation:
Choosing i = 0, j = 1, and k = 2 gives:
|10 - 8| + |-5 - (-5)| = 2 + 0 = 2.
Choosing i = 0, j = 0, and k = 2 gives:
|10 - 2| + |-5 - 8| = 8 + 13 = 21.
This is the maximum possible L1 distance.

Edge Cases

• len(A) == 1 or len(B) == 1: The only possible length is k = 1.
• Identical arrays: If all compared elements are equal, the distance could be 0.