t**g
发帖数: 1164 | 1 如何找出subarray，使得元素之和最大
比如{-2,3,-1,3,-4}
那么答案应该是{3,-1,3}
感觉有点复杂，求教！ | g**e
发帖数: 6127 | 2 这题也应该置顶
google is your best friend
【在 t**g 的大作中提到】
: 如何找出subarray，使得元素之和最大
: 比如{-2,3,-1,3,-4}
: 那么答案应该是{3,-1,3}
: 感觉有点复杂，求教！
| l*****a
发帖数: 14598 | 3 东部公司基本上用不上这种题吧？
准备西行了？
【在 t**g 的大作中提到】
: 如何找出subarray，使得元素之和最大
: 比如{-2,3,-1,3,-4}
: 那么答案应该是{3,-1,3}
: 感觉有点复杂，求教！
| l*****a
发帖数: 14598 | 4 你都想出来最关键的了
为什么还来问
就是n3 ah
【在 t**g 的大作中提到】
: 如何找出subarray，使得元素之和最大
: 比如{-2,3,-1,3,-4}
: 那么答案应该是{3,-1,3}
: 感觉有点复杂，求教！
| J***u
发帖数: 18 | 5 DP。 假设给定数组是a[]
先判断a[]是不是全是non-positive,如果是的话，找出最大的数并返回。
否则dp[0] = a[0], dp[i] = max((dp[i-1] + dp[i]), 0); 然后扫一遍dp[]找最大的
数作为返回subarray的重点，再向左找第一个0后面的位置作为起始,如果左侧找不到0
就以a[0]为起始。O(n)。
看标题还以为是之前听说的非负m*n矩阵找最大子矩阵。。。 | h**********9
发帖数: 3252 | 6
拍脑袋想出了这个办法：
从头到尾扫一遍：
1. 如果碰到连续的负数，将其合并；
2. 如果碰到连续的正数，将其合并；
3. 然后
while (a[i-2] + a[i-1] > 0 && a[i] + a[i-1] > 0) {
合并 a[i-2],a[i-1],a[i];
i = i - 2;
}
4. move on to next item and repeat the same sequence.
【在 t**g 的大作中提到】
: 如何找出subarray，使得元素之和最大
: 比如{-2,3,-1,3,-4}
: 那么答案应该是{3,-1,3}
: 感觉有点复杂，求教！
| h*******e
发帖数: 1377 | 7 是matrix找 sub matrix 還是 array 找連續subarray 前者 o(n^3) 後者 o(n)
都是用dp啊 | a********x
发帖数: 1502 | 8 http://blog.csdn.net/linulysses/article/details/5594141
【在 t**g 的大作中提到】
: 如何找出subarray，使得元素之和最大
: 比如{-2,3,-1,3,-4}
: 那么答案应该是{3,-1,3}
: 感觉有点复杂，求教！
| d******0
发帖数: 191 | 9 Seems old question. Am I right?
Scan from head to tail add if current sum is still positive
Update max sum if possible.
Once current sum is below zero, remove former part until it is positive
again. |
|
