Dynamic Programming

1
import java.util.Arrays;
2

3

4
public int fn(int[] arr) {
5
    if (BASE_CASE) {
6
        return 0;
7
    }
8

9
    int[] dp = new int[STATE_FOR_WHOLE_INPUT + 1];
10
    Arrays.fill(dp, BASE_CASE);
11

12
    for (int STATE = SMALLEST_SUBPROBLEM; STATE <= STATE_FOR_WHOLE_INPUT; STATE++) {
13
        if (BASE_CASE) {
14
            dp[STATE] = BASE_CASE;
15
        } else {
16
            dp[STATE] = RECURRENCE_RELATION(STATE);
17
        }
18
    }
19

20
    return dp[STATE_FOR_WHOLE_INPUT];
21
}

1
public int kadane(int[] arr) {
2
    int currSub = arr[0];
3
    int maxSub = arr[0];
4

5
    for (int i = 1; i < arr.length; i++) {
6
        currSub = Math.max(currSub + arr[i], arr[i]);
7
        maxSub = Math.max(maxSub, currSub);
8
    }
9

10
    return maxSub;
11
}

1
import java.util.HashMap;
2
import java.util.Map;
3

4

5
Map<STATE, Integer> memo = new HashMap<>();
6

7
public int fn(int[] arr) {
8
    return dp(STATE_FOR_WHOLE_INPUT, arr);
9
}
10

11
public int dp(STATE, int[] arr) {
12
    if (BASE_CASE) {
13
        return 0;
14
    }
15

16
    if (memo.contains(STATE)) {
17
        return memo.get(STATE);
18
    }
19

20
    int ans = RECURRENCE_RELATION(STATE);
21
    memo.put(STATE, ans);
22
    return ans;
23
}