How should I practice Maximum L1 Distance Between Equal-Length Subarrays?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The D. E. Shaw Group phone screen problems in FastPrep.

Is Maximum L1 Distance Between Equal-Length Subarrays associated with The D. E. Shaw Group?

FastPrep tags this as a The D. E. Shaw Group phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Maximum L1 Distance Between Equal-Length Subarrays

Learn this problem

● Medium

The D. E. Shaw GroupFULLTIMEPHONE SCREEN

Problem statement

Given two integer arrays a and b, choose one nonempty contiguous subarray from each array. The two chosen subarrays must have the same length, but they may start at different indices.

If the chosen subarrays start at indices i and j and have length length, their L1 distance is

|a[i] - b[j]| + |a[i + 1] - b[j + 1]| + ... + |a[i + length - 1] - b[j + length - 1]|

Return the maximum possible L1 distance. A subarray of length 1 is valid.

Function

maxL1Distance(a: int[], b: int[]) → long

Examples

Example 1

a = [1,3,2]b = [4,2]return = 4

Choose [1,3] from a and [4,2] from b. Their distance is |1 - 4| + |3 - 2| = 3 + 1 = 4.

Example 2

a = [100,0]b = [100,-100]return = 200

Choose the length-1 subarrays [100] from the start of a and [-100] from the end of b. Their distance is 200.

Example 3

a = [-3,4]b = [1,-2,5]return = 10

Align [-3,4] with [1,-2]. The distance is |-3 - 1| + |4 - (-2)| = 4 + 6 = 10, which is maximal.

Constraints

1 <= a.length, b.length <= 2000
-10^9 <= a[i], b[i] <= 10^9
The answer fits in a signed 64-bit integer.