dp[i] = max(dp[i], dp[i-j]*(j-1)) j in [3, i)

```
public int maxA(int N) {
int[] dp = new int[N+1];
for(int i=1;i<=N;i++){
dp[i] = i;
for(int j=3;j<i;j++){
dp[i] = Math.max(dp[i], dp[i-j] * (j-1));
}
}
return dp[N];
}
```

This one is O(n), inspired by paulalexis58. We don't have to run the second loop between [3,i). Instead, we only need to recalculate the last two steps. It's interesting to observe that dp[i - 4] * 3 and dp[i - 5] * 4 always the largest number in the series. Welcome to add your mathematics proof here.

```
public int maxA(int N) {
if (N <= 6) return N;
int[] dp = new int[N + 1];
for (int i = 1; i <= 6; i++) {
dp[i] = i;
}
for (int i = 7; i <= N; i++) {
dp[i] = Math.max(dp[i - 4] * 3, dp[i - 5] * 4);
// dp[i] = Math.max(dp[i - 4] * 3, Math.max(dp[i - 5] * 4, dp[i - 6] * 5));
}
return dp[N];
}
```