J*******g 发帖数: 381 | 1 一个正负整数组成的数组,要求找到使所有元素之和最大的子数组,请问这个问题怎么
做啊? |
t*s 发帖数: 1504 | 2 挑出所有正数
【在 J*******g 的大作中提到】 : 一个正负整数组成的数组,要求找到使所有元素之和最大的子数组,请问这个问题怎么 : 做啊?
|
r**m 发帖数: 163 | 3 我猜题目中数组有序,而且想找出连续的一段数组使其和最大。
【在 t*s 的大作中提到】 : 挑出所有正数
|
g*****g 发帖数: 34805 | 4 老得不行的题了,google吧。
【在 r**m 的大作中提到】 : 我猜题目中数组有序,而且想找出连续的一段数组使其和最大。
|
J*******g 发帖数: 381 | 5 数组是无序的,不过是要找一段连续的子数组。
【在 r**m 的大作中提到】 : 我猜题目中数组有序,而且想找出连续的一段数组使其和最大。
|
M*****a 发帖数: 2054 | 6 不就是简单动态规划么
【在 J*******g 的大作中提到】 : 数组是无序的,不过是要找一段连续的子数组。
|
g*****g 发帖数: 34805 | 7 这个问题比较简单,不需要动态规划。O(N)复杂度而已。
【在 M*****a 的大作中提到】 : 不就是简单动态规划么
|
w*****y 发帖数: 264 | 8 有这么简单吗?子数组的大小不是确定的
【在 g*****g 的大作中提到】 : 这个问题比较简单,不需要动态规划。O(N)复杂度而已。
|
h*******e 发帖数: 225 | 9 yes. scanning the array in one pass is enough. this is a classic problem.
you can find the solution on every interview problem forum.
【在 w*****y 的大作中提到】 : 有这么简单吗?子数组的大小不是确定的
|
s*****g 发帖数: 5159 | 10 动态规划解partition类问题的要求是最优解里面的元素满足某种给定的顺序,你这顺序
早已给定,不用自己找,所以肯定能解。
慢慢做多了就体会到了,先不给你答案。
【在 w*****y 的大作中提到】 : 有这么简单吗?子数组的大小不是确定的
|
|
|
r*******n 发帖数: 3020 | 11 这个问题也是典型的动态规划问题,
没有说O(n)就不是动态规划。
pls correct me if I was wrong.
【在 g*****g 的大作中提到】 : 这个问题比较简单,不需要动态规划。O(N)复杂度而已。
|
g*****g 发帖数: 34805 | 12 当你不需要写递归式的时候就不能算动态规划。
否则就跟一次方程式难道不算二次方程式一样。
【在 r*******n 的大作中提到】 : 这个问题也是典型的动态规划问题, : 没有说O(n)就不是动态规划。 : pls correct me if I was wrong.
|
s*x 发帖数: 3328 | |
s*x 发帖数: 3328 | 14 可以用动态规划作,但是那样复杂度就不是O(n)了。 |
K****n 发帖数: 5970 | 15 嗯,典型例题
【在 M*****a 的大作中提到】 : 不就是简单动态规划么
|
t******e 发帖数: 1293 | 16 from <>
int maxsofar = 0;
int maxendinghere = 0;
for (int i = 0; i < n; ++i)
{
maxendinghere = max(maxendinghere + a[i], 0);
maxsofar = max(maxsofar, maxendinghere);
}
【在 J*******g 的大作中提到】 : 一个正负整数组成的数组,要求找到使所有元素之和最大的子数组,请问这个问题怎么 : 做啊?
|
s*****g 发帖数: 5159 | 17 really pearl:)
【在 t******e 的大作中提到】 : from <> : int maxsofar = 0; : int maxendinghere = 0; : for (int i = 0; i < n; ++i) : { : maxendinghere = max(maxendinghere + a[i], 0); : maxsofar = max(maxsofar, maxendinghere); : }
|
s*********l 发帖数: 103 | 18 It does not cover the cases where the array only contains negative numbers. (unless the empty set is the expected answer)
【在 t******e 的大作中提到】 : from <> : int maxsofar = 0; : int maxendinghere = 0; : for (int i = 0; i < n; ++i) : { : maxendinghere = max(maxendinghere + a[i], 0); : maxsofar = max(maxsofar, maxendinghere); : }
|