leetcode

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

1031.cpp (1145B)

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