leetcode

Solution to some Leetcode problems written in C++

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

1031.cpp (1145B)

0 class Solution { 1 static int prefix[1001], suffix[1001]; 2 static int n; 3 4 int solve(const int firstLen, const int secondLen) const { 5 static int left[1001], right[1001]; 6 7 left[firstLen - 1] = right[n - secondLen + 1] = 0; 8 for (int i = firstLen; i <= n; i++) 9 left[i] = max(left[i - 1], prefix[i] - prefix[i - firstLen]); 10 for (int i = n - secondLen; i >= 0; i--) 11 right[i] = max(right[i + 1], suffix[i] - suffix[i + secondLen]); 12 13 int res = 0; 14 for (int i = firstLen; i <= n - secondLen; i++) 15 res = max(res, left[i] + right[i]); 16 return res; 17 } 18 19 public: 20 int maxSumTwoNoOverlap(const vector<int> &nums, int firstLen, int secondLen) const { 21 n = nums.size(); 22 23 prefix[0] = 0, suffix[n] = 0; 24 for (int i = 0, acc = 0; i < n; i++) 25 prefix[i + 1] = acc += nums[i]; 26 for (int i = n - 1, acc = 0; i >= 0; i--) 27 suffix[i] = acc += nums[i]; 28 29 return max(solve(firstLen, secondLen), solve(secondLen, firstLen)); 30 } 31 }; 32 33 int Solution::prefix[1001]; 34 int Solution::suffix[1001]; 35 int Solution::n;