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);
: }
|
