@sweetteaoh Because when nums is empty, if you don't check this condition then you will return index 0.
Spin0za
@Spin0za
Posts made by Spin0za

RE: Pretty short C++/Java/Ruby/Python

RE: Please explain why [1,2,3,4,5] is correct
@Yang_BU Why is it false? The problem doesn't say that you must split the array into 2 or more subsequences. [1,2,3,4,5] itself is a subsequence.

RE: How do you come up with the greedy strategy?
@zshen9 I explained to you in my 2nd paragraph. Once you copypaste, you won't want to type a single A anymore, you'd rather do it earlier. This is an exchange argument.

RE: How do you come up with the greedy strategy?
You sure your conclusion is right? For N = 11, the optimal sequence is AAA, CtrlA, CtrlC, CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV. Select and copy appear twice.
If you mean a single A won't ever appear after a copypaste, this is apparent since you always would move this single A before the copypaste so that you gain at least one more A.

RE: Two Java DP solution O(n^2) and O(n)
I wrote a proof of the linear time method. Happy to discuss :)
https://discuss.leetcode.com/topic/97721/mathematicalproofoftheonsolution

Mathematical proof of the O(N) solution
The reason we could use
dp[i] = max(dp[i4]*3, dp[i5]*4)
instead ofdp[i] = max(dp[i3]*2, dp[i4]*3, dp[i5]*4, dp[i6]*5, ...)
is the following property:When
i >= 6
, we have5/4 * dp[i] <= dp[i+1] <= 3/2 * dp[i]
.We prove it using strong mathematical induction. Base case is trivial:
dp[6] = 6, dp[7] = 9, dp[8] = 12
.
Now assume5/4 * dp[i] <= dp[i+1] <= 3/2 * dp[i]
for alli >= 6 && i < n
, we prove5/4 * dp[n] <= dp[n+1] <= 3/2 * dp[n]
. By the given DP formula,dp[n+1] = max(dp[n2]*2, dp[n3]*3, dp[n4]*4, dp[n5]*5, ...)
. We havedp[n3]*3 >= dp[n2]*2
becausedp[i+1] <= 3/2 * dp[i]
holds wheni = n3
. Similarly, we havedp[n4]*4 >= dp[n5]*5
becausedp[i+1] >= 5/4 * dp[i]
holds wheni = n5
.
Now the key part: for allk >= 5 && k < n
, we havedp[n4]*4 >= dp[nk]*k
i.e.dp[n4] >= k/4 * dp[nk]
becausedp[n4] >= 5/4 * dp[n5] >= (5/4)^2 * dp[n6] >= ... >= (5/4)^j * dp[nj4]
. Now letj = k4
, we getdp[n4] >= (5/4)^(k4) * dp[nk] = (1 + 1/4)^(k4) * dp[nk] >= (1 + 1/4 * (k  4)) * dp[nk] = k/4 * dp[nk]
, by the Bernoulli inequality. Proof complete.(To be ultimately rigorous, I actually have to prove
dp[n5] >= k/5 * dp[nk]
anddp[n4] >= 5/4 * dp[n5]
separately, due to thei >= 6
limit in the property. But I'd rather keep the proof simpler.)