1
class Solution {
2
  public int maxSumAfterPartitioning(int[] arr, int k) {
3
    return maxSum(arr, k, 0);
4
  }
5

6
  public int maxSum(int[] arr, int k, int start) {
7
    int curr1 = 0, curr2 = 0;
8
    int prev = 0;
9
    int max = 0;
10

11
    Map<String, Integer> memo = new HashMap();
12
    // memo.put("0,0", arr[0]);
13

14
    for (int i = 0; i < arr.length; ++i) {
15
      // without current element
16
      curr1 = prev + arr[i];
17

18
      // with current element, find max if p=0...k (since subarray can be longeth of at most k)
19
      int tempk = 0, half1 = 0, half2 = 0, temp = 0;
20
      for (int p = 0; p <= k; ++p) {
21
        half1 = findMaxSumWithKEle(arr, p, i);
22
        tempk = i - p;
23
        half2 = memo.get(("0," + tempk)) == null ? 0 : memo.get(("0," + tempk));
24
        if (temp < half1 + half2) {
25
          temp = half1 + half2;
26
        }
27
      }
28

29
      curr2 = temp;
30

31
      // find max between curr1 or curr2 - with current elemtn in the subarray or outside the
32
      // subarray
33
      max = (curr1 < curr2) ? curr2 : curr1;
34

35
      // add in memo
36
      String key = "0," + i;
37
      memo.put(key, max);
38
      System.out.println("Max: " + max + " from [" + key + "]");
39
      prev = max;
40
    }
41

42
    return max;
43
  }
44

45
  public static Integer findMaxSumWithKEle(int[] arr, int k, int end) {
46
    int max = 0;
47
    if (end > arr.length || end < 0) {
48
      return 0;
49
    }
50
    int c = 0;
51
    for (int i = end; i > (end - k) && i >= 0; --i) {
52
      ++c;
53
      if (max < arr[i]) {
54
        max = arr[i];
55
      }
56
    }
57
    return max * c;
58
  }
59
}