leetcode

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;