Leetcode Problem 1031. Maximum Sum of Two Non-Overlapping Subarrays

1031. Maximum Sum of Two Non-Overlapping Subarrays

Leetcode Solutions

Prefix Sum and Sliding Window

  1. Calculate the prefix sum array of the input array nums.
  2. Initialize variables to keep track of the maximum sum found so far.
  3. Use a sliding window to find the maximum sum of a subarray of length firstLen.
  4. For each window position, calculate the sum of the current window using the prefix sum array.
  5. Find the maximum sum of a non-overlapping subarray of length secondLen that comes before the current window.
  6. Find the maximum sum of a non-overlapping subarray of length secondLen that comes after the current window.
  7. Update the maximum sum found so far with the larger of the two sums found in steps 5 and 6.
  8. Repeat steps 3 to 7 after swapping the values of firstLen and secondLen.
  9. Return the maximum sum found.
UML Thumbnail

Brute Force with Precomputed Sums

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...