leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0689.cpp (1166B)

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