2024-12-28 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 28

Description

Maximum Sum of 3 Non-Overlapping Subarrays

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

class Solution {
  using ll = long long;
public:
  vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    int len = nums.size();
    vector<ll> sumK(len);
    for(int i = 0; i < k; ++i) {
      sumK[0] += nums[i];
    }
    for(int i = 1; i + k - 1 < len; ++i) {
      sumK[i] = sumK[i - 1] - nums[i - 1] + nums[i + k - 1];
    }
    vector<pair<ll, pair<int, int>>> dp(len);
    priority_queue<pair<ll, int>> pq1;
    priority_queue<pair<ll, pair<int, int>>> pq2;
    int answerSum = 0;
    vector<int> answerPos = {0, 0, 0};
    for(int i = k; i + k - 1 < len; ++i) {
      pq1.push({sumK[i - k], len - (i - k)});
      dp[i] = dp[i - 1];
      if(sumK[i] + pq1.top().first > dp[i - 1].first) {
        dp[i].first = sumK[i] + pq1.top().first;
        dp[i].second = make_pair(pq1.top().second, len - i);
      }
      if(i >= k * 2) {
        pq2.push(dp[i - k]);
        if(sumK[i] + pq2.top().first > answerSum) {
          answerSum = sumK[i] + pq2.top().first;
          answerPos[0] = len - pq2.top().second.first;
          answerPos[1] = len - pq2.top().second.second;
          answerPos[2] = i;
        }
      }
    }
    return answerPos;
  }
};

// Accepted
// 43/43 cases passed (11 ms)
// Your runtime beats 33.6 % of cpp submissions
// Your memory usage beats 21.41 % of cpp submissions (34.9 MB)
Algorithm