Maximum Sum of Two Non-Overlapping Subarrays LeetCode solution in Java

1
class Solution {
2
  public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
3
    int[] dp1 = new int[nums.length];
4
    int[] dp2 = new int[nums.length];
5

6
    int sum = 0;
7
    for (int i = 0; i < nums.length; i++) {
8
      if (i < firstLen) {
9
        sum += nums[i];
10
        dp1[i] = sum;
11
      } else {
12
        sum += nums[i] - nums[i - firstLen];
13
        dp1[i] = Math.max(sum, dp1[i - 1]);
14
      }
15
    }
16

17
    sum = 0;
18
    for (int i = nums.length - 1; i >= 0; i--) {
19
      if (i + secondLen >= nums.length) {
20
        sum += nums[i];
21
        dp2[i] = sum;
22
      } else {
23
        sum += nums[i] - nums[i + secondLen];
24
        dp2[i] = Math.max(sum, dp2[i + 1]);
25
      }
26
    }
27

28
    int max = 0;
29

30
    for (int i = firstLen - 1; i < nums.length - secondLen; i++) {
31
      max = Math.max(max, dp1[i] + dp2[i + 1]);
32
    }
33

34
    int max1 = max;
35

36
    dp1 = new int[nums.length];
37
    dp2 = new int[nums.length];
38

39
    sum = 0;
40
    for (int i = 0; i < nums.length; i++) {
41
      if (i < secondLen) {
42
        sum += nums[i];
43
        dp1[i] = sum;
44
      } else {
45
        sum += nums[i] - nums[i - secondLen];
46
        dp1[i] = Math.max(sum, dp1[i - 1]);
47
      }
48
    }
49

50
    sum = 0;
51
    for (int i = nums.length - 1; i >= 0; i--) {
52
      if (i + firstLen >= nums.length) {
53
        sum += nums[i];
54
        dp2[i] = sum;
55
      } else {
56
        sum += nums[i] - nums[i + firstLen];
57
        dp2[i] = Math.max(sum, dp2[i + 1]);
58
      }
59
    }
60

61
    max = 0;
62

63
    for (int i = secondLen - 1; i < nums.length - firstLen; i++) {
64
      max = Math.max(max, dp1[i] + dp2[i + 1]);
65
    }
66

67
    int max2 = max;
68

69
    return Math.max(max1, max2);
70
  }
71
}