leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0689.cpp (1166B)

      1 class Solution {
      2   public:
      3     vector<int> maxSumOfThreeSubarrays(const vector<int> &nums, int k) const {
      4         const int n = nums.size();
      5 
      6         static int sum[4][20003], index[4][20003];
      7         static int prefix[20003];
      8 
      9         for (int i = 1; i <= n; i++) {
     10             prefix[i] = prefix[i - 1] + nums[i - 1];
     11         }
     12 
     13         memset(sum, 0x00, sizeof(sum));
     14         memset(index, 0x00, sizeof(index));
     15         for (int cnt = 1; cnt <= 3; cnt++) {
     16             for (int end = k * cnt; end <= n; end++) {
     17                 const int currentSum = prefix[end] - prefix[end - k] + sum[cnt - 1][end - k];
     18 
     19                 if (currentSum > sum[cnt][end - 1]) {
     20                     sum[cnt][end] = currentSum;
     21                     index[cnt][end] = end - k;
     22                 } else {
     23                     sum[cnt][end] = sum[cnt][end - 1];
     24                     index[cnt][end] = index[cnt][end - 1];
     25                 }
     26             }
     27         }
     28 
     29         int end = n;
     30         vector<int> result(3, 0);
     31         for (int idx = 3; idx >= 1; idx--) {
     32             result[idx - 1] = index[idx][end];
     33             end = result[idx - 1];
     34         }
     35 
     36         return result;
     37     }
     38 };