@sweetteaoh Because when nums is empty, if you don't check this condition then you will return index 0.
Posts made by Spin0za
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?
You sure your conclusion is right? For N = 11, the optimal sequence is AAA, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V. Select and copy appear twice.
If you mean a single A won't ever appear after a copy-paste, this is apparent since you always would move this single A before the copy-paste 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 :)
Mathematical proof of the O(N) solution
The reason we could use
dp[i] = max(dp[i-4]*3, dp[i-5]*4)instead of
dp[i] = max(dp[i-3]*2, dp[i-4]*3, dp[i-5]*4, dp[i-6]*5, ...)is the following property:
i >= 6, we have
5/4 * dp[i] <= dp[i+1] <= 3/2 * dp[i].
We prove it using strong mathematical induction. Base case is trivial:
dp = 6, dp = 9, dp = 12.
5/4 * dp[i] <= dp[i+1] <= 3/2 * dp[i]for all
i >= 6 && i < n, we prove
5/4 * dp[n] <= dp[n+1] <= 3/2 * dp[n]. By the given DP formula,
dp[n+1] = max(dp[n-2]*2, dp[n-3]*3, dp[n-4]*4, dp[n-5]*5, ...). We have
dp[n-3]*3 >= dp[n-2]*2because
dp[i+1] <= 3/2 * dp[i]holds when
i = n-3. Similarly, we have
dp[n-4]*4 >= dp[n-5]*5because
dp[i+1] >= 5/4 * dp[i]holds when
i = n-5.
Now the key part: for all
k >= 5 && k < n, we have
dp[n-4]*4 >= dp[n-k]*ki.e.
dp[n-4] >= k/4 * dp[n-k]because
dp[n-4] >= 5/4 * dp[n-5] >= (5/4)^2 * dp[n-6] >= ... >= (5/4)^j * dp[n-j-4]. Now let
j = k-4, we get
dp[n-4] >= (5/4)^(k-4) * dp[n-k] = (1 + 1/4)^(k-4) * dp[n-k] >= (1 + 1/4 * (k - 4)) * dp[n-k] = k/4 * dp[n-k], by the Bernoulli inequality. Proof complete.
(To be ultimately rigorous, I actually have to prove
dp[n-5] >= k/5 * dp[n-k]and
dp[n-4] >= 5/4 * dp[n-5]separately, due to the
i >= 6limit in the property. But I'd rather keep the proof simpler.)