Two Java DP solution O(n^2) and O(n)

• 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];
}
``````

• For the O(n) solution:

Interesting thing is the third term `dp[i - 6] * 5` can be removed...

`dp[i - 3] * 2` is always smaller than the others.

Can anyone prove or explain these?

• @realhly88
You are right! Have changed my post to only recalculate last two steps.

• This post is deleted!

• I wrote a proof of the linear time method. Happy to discuss :)

https://discuss.leetcode.com/topic/97721/mathematical-proof-of-the-o-n-solution

• This post is deleted!

• `i` start from 2 got AC.

``````class Solution(object):
def maxA(self, N):
"""
:type N: int
:rtype: int
"""
dp = [0] * (N + 1)
for i in range(N + 1):
dp[i] = i
for j in range(2, i):
dp[i] = max(dp[i], dp[i - j] * (j - 1))
return dp[N]
``````

• Hi, thank you for your contribution!
One question, should we consider the situation that multiple Ctrl-A being used, that means the 'A' typed will be increased in square. At least, the mathematics proof is needed to show that it is never this case could generate the maximum number of 'A', Thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.