DEV Community

Cover image for 689. Maximum Sum of 3 Non-Overlapping Subarrays
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1

689. Maximum Sum of 3 Non-Overlapping Subarrays

689. Maximum Sum of 3 Non-Overlapping Subarrays

Difficulty: Hard

Topics: Array, Dynamic Programming

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example 1:

  • Input: nums = [1,2,1,2,6,7,5,1], k = 2
  • Output: [0,3,5]
  • Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
    • We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

  • Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
  • Output: [0,2,4]

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] < 216
  • 1 <= k <= floor(nums.length / 3)

Solution:

We will use a dynamic programming approach. The idea is to break down the problem into smaller subproblems, leveraging the overlap of subarrays to efficiently calculate the maximum sum of three non-overlapping subarrays of length k.

Approach:

  1. Precompute the sums of subarrays of length k:
    First, we compute the sum of all subarrays of length k in the input array nums. This can be done efficiently in linear time by using a sliding window technique.

  2. Dynamic Programming (DP):
    We create two auxiliary arrays, left and right, to store the indices of the best subarrays found up to the current position. The left[i] will store the index of the best subarray ending before index i, and right[i] will store the index of the best subarray starting after index i.

  3. Iterate and Calculate the Maximum Sum:
    For each possible middle subarray starting at index j, we calculate the total sum by considering the best left subarray before j and the best right subarray after j.

  4. Lexicographical Ordering:
    If there are multiple valid answers (with the same sum), we return the lexicographically smallest one. This is ensured by the order of iteration.

Let's implement this solution in PHP: 689. Maximum Sum of 3 Non-Overlapping Subarrays

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Subarray Sums Calculation:

    • We calculate the sum of all possible subarrays of length k. This is done by first calculating the sum of the first k elements. Then, for each subsequent position, we subtract the element that is left behind and add the next element in the array, making it an efficient sliding window approach.
  2. Left and Right Arrays:

    • left[i] holds the index of the subarray with the maximum sum that ends before index i.
    • right[i] holds the index of the subarray with the maximum sum that starts after index i.
  3. Final Calculation:

    • For each middle subarray j, we check the combination of the best left subarray and the best right subarray, and update the result if the sum is greater than the current maximum.
  4. Lexicographically Smallest Answer:

    • As we iterate from left to right, we ensure the lexicographically smallest solution by naturally choosing the first subarrays that yield the maximum sum.

Example:

For the input:

$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;
Enter fullscreen mode Exit fullscreen mode

The output will be:

[0, 3, 5]
Enter fullscreen mode Exit fullscreen mode

This approach ensures that the time complexity remains efficient, with a time complexity of approximately O(n), where n is the length of the input array nums.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Transforming Interviews into Publishable Stories with AssemblyAI

Insightview is a modern web application that streamlines the interview workflow for journalists. By leveraging AssemblyAI's LeMUR and Universal-2 technology, it transforms raw interview recordings into structured, actionable content, dramatically reducing the time from recording to publication.

Key Features:
🎥 Audio/video file upload with real-time preview
🗣️ Advanced transcription with speaker identification
⭐ Automatic highlight extraction of key moments
✍️ AI-powered article draft generation
📤 Export interview's subtitles in VTT format

Read full post

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay