0681-0690

681. Next Closest Time $\star\star$

682. Baseball Game $\star$

683. K Empty Slots $\star\star\star$

684. Redundant Connection $\star\star$

685. Redundant Connection II $\star\star\star$

686. Repeated String Match $\star$

687. Longest Univalue Path $\star$

688. Knight Probability in Chessboard $\star\star$

689. Maximum Sum of 3 Non-Overlapping Subarrays $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    vector<int> ans = {-1, -1, -1};
    int subarrayCount = nums.size() - k + 1;
    vector<int> dp(subarrayCount);
    int sum = 0;

    for (int i = 0; i < nums.size(); ++i) {
      sum += nums[i];
      if (i >= k) sum -= nums[i - k];
      if (i >= k - 1) dp[i - k + 1] = sum;
    }

    vector<int> left(subarrayCount);
    int maxIndex = 0;

    for (int i = 0; i < subarrayCount; ++i) {
      if (dp[i] > dp[maxIndex]) maxIndex = i;
      left[i] = maxIndex;
    }

    vector<int> right(subarrayCount);
    maxIndex = subarrayCount - 1;

    for (int i = subarrayCount - 1; i >= 0; --i) {
      if (dp[i] >= dp[maxIndex]) maxIndex = i;
      right[i] = maxIndex;
    }

    for (int i = k; i < subarrayCount - k; ++i)
      if (ans[0] == -1 || dp[left[i - k]] + dp[i] + dp[right[i + k]] >
                              dp[ans[0]] + dp[ans[1]] + dp[ans[2]])
        ans = {left[i - k], i, right[i + k]};

    return ans;
  }
};

690. Employee Importance $\star$