Leetcode

1031. Maximum Sum of Two Non-Overlapping Subarrays

Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M.  (For clarification, the L-length subarray could occur before or after the M-length subarray.)

Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:

  • 0 <= i < i + L - 1 < j < j + M - 1 < A.length, or
  • 0 <= j < j + M - 1 < i < i + L - 1 < A.length.

 

Example 1:

Input: 

A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2

Output: 

20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: 

A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2

Output: 

29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: 

A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3

Output: 

31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

 

Note:

  1. L >= 1
  2. M >= 1
  3. L + M <= A.length <= 1000
  4. 0 <= A[i] <= 1000
class Solution {

    /**
     * @param Integer[] $A
     * @param Integer $L
     * @param Integer $M
     * @return Integer
     */
    function maxSumTwoNoOverlap($A, $L, $M) {
        $max  = 0;
        $a = [];
        $b = [];
        for($i  = 0; $i < count($A)-$L+1; $i ++){
            $a[$i] =  array_sum(array_slice($A,$i,$L));
        }
        
        for($j = 0; $j < count($A)-$M+1; $j ++){
            $b[$j] = array_sum(array_slice($A,$j,$M));
        }
        arsort($a);arsort($b);
        foreach($a as $ak => $av){
            foreach($b as $bk => $bv){
                if($bk + $M <= $ak || $ak + $L <= $bk){
                    $max = max($max, $av + $bv);

                }
            }
        }
        
        return $max;
    }
}

160ms

Thoughts:

  • My code is the version used for contest, so..
  • The length of inputs (1000) seems relatively small, so just follow your heart, again…
  • Idea, scan & store sums for L &  M fixed size arrays.
  • for each sum L and for each sum M, if no overlap, the check and update max total.
  • What makes it slow:
    • array_sum.. fixed size sliding door works better, but more codes…
    • double for each, there’s an obvious pattern to move index out of overlap.
  • Having these sorts have 10ms improvement, which is quite interesting.

Improved Version

class Solution {

    /**
     * @param Integer[] $A
     * @param Integer $L
     * @param Integer $M
     * @return Integer
     */
    function maxSumTwoNoOverlap($A, $L, $M) {
        $max  = 0;
        $a = [];
        $b = [];

        for($i  = 0; $i < count($A)-$L+1; $i ++){
            if($i == 0){
                $a[$i] =  array_sum(array_slice($A,$i,$L));
            } else {
                $a[$i] = $a[$i-1] - $A[$i-1] + $A[$i+$L-1];
            }
        }
        
        for($i = 0; $i < count($A)-$M+1; $i ++){
            if($i == 0){
                $b[$i] =  array_sum(array_slice($A,$i,$M));
            } else {
                $b[$i] = $b[$i-1] - $A[$i-1] + $A[$i+$M-1];
            }
        }
        for($i = 0; $i < count($a); $i++){
            for($j = 0; $j < count($b);$j++){
                if($j + $M <= $i || $i + $L <= $j){
                    $max = max($max, $a[$i] + $b[$j]);
                } else if($j + $M <= $i){
                    $j += ($M-1);
                }
            }
        }
        
        return $max;
    }
}
  • The “fixed size sliding door” saved about 20ms
  • No significant improvement for the double for each.