leetcode

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 };