r*****e
发帖数: 30 | |
Q**F
发帖数: 995 | |
r*****e
发帖数: 30 | |
y*****u
发帖数: 29 | |
s*********3
发帖数: 25 | 5 facebook 那题的一个思路。
1. 先用一个MaxSum[i][j], 用来记录array中 i 到j的连续的最大和。是一个DP问题。
2. 再用maxSum[i][j]， 整个问题f(k, n) = max{f(k - 1, n - i), i<(n-i-k, n)}。 |
d****n
发帖数: 233 | 6 前不久刚做过， posted on my blogger:
http://codeanytime.blogspot.com/2014/12/lintcode-maximum-subarr
【在 s*********3 的大作中提到】
: facebook 那题的一个思路。
: 1. 先用一个MaxSum[i][j], 用来记录array中 i 到j的连续的最大和。是一个DP问题。
: 2. 再用maxSum[i][j]， 整个问题f(k, n) = max{f(k - 1, n - i), i<(n-i-k, n)}。
|
w****k
发帖数: 755 | 7 2nd:
This is similar to The Painter’s Partition Problem. DP formula is
M[n, k] = Max{ M[j, k-1] + S(j) } , j=k-1..n
We divide the n values into two parts first. The first half is 0 to j-1 and
the 2nd from j to n-1. The 1st half should be sub-divided into k-1 parts and
the 2nd a single part. The value of 2nd half, S(j), is actually the max sum
from j to n-1.
Note that there cannot be empty partition. |
j**********g
发帖数: 77 | |
y*****i
发帖数: 141 | |
t**r
发帖数: 3428 | |
w****a
发帖数: 710 | 11 第二题不是max sum plus plus么。HDOJ有 |
m********8
发帖数: 44 | 12 哈哈这第一题比较奇葩因为有数字取值是从1-100的限制所有可以用二维DP，要是没这
个限制我觉得都没法DP只能用search。
dp[i][v] 表示前i个数中第i个数调整为v同时满足相邻两数小于target的最小cost。（
v的取值为1-100）.
dp[i][v] = min(dp[i - 1][v'] + |A[i] - v|where |v - v'| <= target). |
l*****8
发帖数: 1083 | 13 这题太奇葩了，如此dp，怎么想到的？
【在 m********8 的大作中提到】
: 哈哈这第一题比较奇葩因为有数字取值是从1-100的限制所有可以用二维DP，要是没这
: 个限制我觉得都没法DP只能用search。
: dp[i][v] 表示前i个数中第i个数调整为v同时满足相邻两数小于target的最小cost。（
: v的取值为1-100）.
: dp[i][v] = min(dp[i - 1][v'] + |A[i] - v|where |v - v'| <= target).
|
m********8
发帖数: 44 | 14 要不是碰到过类似题目，打死我估计也想不到。。。而且估计在面试的时间里也很少有
人能想到，这种题目要是真做面试题拿来黑人挺好的。
【在 l*****8 的大作中提到】
: 这题太奇葩了，如此dp，怎么想到的？
|
