m*****g
发帖数: 226 | 1 貌似经典的DP
given an array of ints, find the contiguous sequence with maximum sum.
我是把每个可能的组合都试的，做出来(n2)的时间
请问DP得怎么做 |
j***n
发帖数: 301 | 2 这题很老了，貌似不是DP。
从最开始做累加，用一个sum变量记录累加结果。再用一个maxsum记录最大值。sum为负
的时候就清零。线性复杂度
【在 m*****g 的大作中提到】
: 貌似经典的DP
: given an array of ints, find the contiguous sequence with maximum sum.
: 我是把每个可能的组合都试的，做出来(n2)的时间
: 请问DP得怎么做
|
m*****g
发帖数: 226 | 3 sum 为负清零。
如果后面的累加结果能把之前的负数抵消，难道不是应该一起算上去么 |
j***n
发帖数: 301 | 4 加上一个负数，总不如不加大吧
【在 m*****g 的大作中提到】
: sum 为负清零。
: 如果后面的累加结果能把之前的负数抵消，难道不是应该一起算上去么
|
r****o
发帖数: 1950 | 5 谁能谈谈这道题的变种怎么作，
数组里面找一段连续元素的子数组，使其product最大。当然，元素有正有负。
【在 j***n 的大作中提到】
: 这题很老了，貌似不是DP。
: 从最开始做累加，用一个sum变量记录累加结果。再用一个maxsum记录最大值。sum为负
: 的时候就清零。线性复杂度
|
m*****g
发帖数: 226 | 6 如果后面有几个正数，能把之前的负数中和
那么就能把负数之前的正数一起放进去了
【在 j***n 的大作中提到】
: 加上一个负数，总不如不加大吧
|
j***n
发帖数: 301 | 7 我有点好奇mustang的平方解法
【在 r****o 的大作中提到】
: 谁能谈谈这道题的变种怎么作，
: 数组里面找一段连续元素的子数组，使其product最大。当然，元素有正有负。
|
j**l
发帖数: 2911 | |
j***n
发帖数: 301 | 9 那样sum不会为负
【在 m*****g 的大作中提到】
: 如果后面有几个正数，能把之前的负数中和
: 那么就能把负数之前的正数一起放进去了
|
m*****g
发帖数: 226 | 10 平方是用一个大小为n的数组存放暂时结果才得到的
【在 j***n 的大作中提到】
: 我有点好奇mustang的平方解法
|
|
|
j***n
发帖数: 301 | 11 能具体点么，数组的每个元素都代表什么？
【在 m*****g 的大作中提到】
: 平方是用一个大小为n的数组存放暂时结果才得到的
|
m*****g
发帖数: 226 | 12 算了
是我自己想复杂了
你那个线性解法挺好。多谢
【在 j***n 的大作中提到】
: 能具体点么，数组的每个元素都代表什么？
|
j***n
发帖数: 301 | 13 呵呵，我的意思是，你的平方解法是否能够用来接jntl同学提出的变种，因为目前为止
我只想到立方解法
【在 m*****g 的大作中提到】
: 算了
: 是我自己想复杂了
: 你那个线性解法挺好。多谢
|
m*****g
发帖数: 226 | 14 应该可以
其实平方解法就是从立方解法里面优化来的
思路就是你不用每次都把所有元素乘一遍
用一个数组(n)把中间值存起来，这样每次只要再乘以一个新元素
所以复杂度只是你需要探索的个数
【在 j***n 的大作中提到】
: 呵呵，我的意思是，你的平方解法是否能够用来接jntl同学提出的变种，因为目前为止
: 我只想到立方解法
|
r****o
发帖数: 1950 | 15 你们是在讨论maximum product的变种吗？
这个变种有没有O(n)的解法?
【在 m*****g 的大作中提到】
: 应该可以
: 其实平方解法就是从立方解法里面优化来的
: 思路就是你不用每次都把所有元素乘一遍
: 用一个数组(n)把中间值存起来，这样每次只要再乘以一个新元素
: 所以复杂度只是你需要探索的个数
|
j***n
发帖数: 301 | 16 OK,知道了
【在 m*****g 的大作中提到】
: 应该可以
: 其实平方解法就是从立方解法里面优化来的
: 思路就是你不用每次都把所有元素乘一遍
: 用一个数组(n)把中间值存起来，这样每次只要再乘以一个新元素
: 所以复杂度只是你需要探索的个数
|
j***n
发帖数: 301 | 17 饿，要是谁有我搬板凳
【在 r****o 的大作中提到】
: 你们是在讨论maximum product的变种吗？
: 这个变种有没有O(n)的解法?
|
b******v
发帖数: 1493 | 18 programming pearls上专门有一章是讲这题的
【在 m*****g 的大作中提到】
: 貌似经典的DP
: given an array of ints, find the contiguous sequence with maximum sum.
: 我是把每个可能的组合都试的，做出来(n2)的时间
: 请问DP得怎么做
|
H*X
发帖数: 281 | 19 programming pearls上有讨论，好像CLRS也有
就是记录2个sum: current sum, current max sum,
把数组扫描一遍，如果current sum < 0，就从0开始重新计算，如果current sum >
current max sum, 那么current max sum = current sum, |
m*****g
发帖数: 226 | |
|
|
H*X
发帖数: 281 | 21
算是DP吧， 因为position i 的sum是position i-1的sum + array[i],
【在 j***n 的大作中提到】
: 这题很老了，貌似不是DP。
: 从最开始做累加，用一个sum变量记录累加结果。再用一个maxsum记录最大值。sum为负
: 的时候就清零。线性复杂度
|
j***n
发帖数: 301 | 22 对，好像是这样
【在 H*X 的大作中提到】
:
: 算是DP吧， 因为position i 的sum是position i-1的sum + array[i],
|
b******v
发帖数: 1493 | 23 可以保存如下变量：
以当前元素结尾的最大乘积lastmax，及其起始范围lastmaxstart, lastmaxend
以当前元素结尾的最小乘积lastmin, 及其起始范围lastminstart, lastminend
当前最大的乘积max, 及其起始范围maxstart, maxend
它们都初始为数组只有第一个元素时对应的值
当有一个新变量a[i]进来时
(1) 如果a[i]>0
把a[i]*lastmax与a[i]进行比较，并更新lastmax及其范围
把a[i]*lastmin与a[i]进行比较，并更新lastmin及其范围
(2) 如果a[i]<0
把a[i]*lastmin与a[i]进行比较，并更新lastmax及其范围
把a[i]*lastmax与a[i]进行比较，并更新lastmin及其范围
(3) 如果a[i]=0
lastmax, lastmin都是0
(4) 当上面三步结束时，将lastmax与max比较，并更新max及其范围
这个算法的时间复杂度显然是O(n)，空间复杂度O(1)
【在 r****o 的大作中提到】
: 谁能谈谈这道题的变种怎么作，
: 数组里面找一段连续元素的子数组，使其product最大。当然，元素有正有负。
|
f****4
发帖数: 1359 | 24 这个好像没有问题
之前提到的立方解法是啥
【在 b******v 的大作中提到】
: 可以保存如下变量：
: 以当前元素结尾的最大乘积lastmax，及其起始范围lastmaxstart, lastmaxend
: 以当前元素结尾的最小乘积lastmin, 及其起始范围lastminstart, lastminend
: 当前最大的乘积max, 及其起始范围maxstart, maxend
: 它们都初始为数组只有第一个元素时对应的值
: 当有一个新变量a[i]进来时
: (1) 如果a[i]>0
: 把a[i]*lastmax与a[i]进行比较，并更新lastmax及其范围
: 把a[i]*lastmin与a[i]进行比较，并更新lastmin及其范围
: (2) 如果a[i]<0
|
b******v
发帖数: 1493 | 25 嗯，我上机试了很多例子，应该没有问题
【在 f****4 的大作中提到】
: 这个好像没有问题
: 之前提到的立方解法是啥
|
r****o
发帖数: 1950 | 26 你说的最小乘积lastmin是指绝对值最大的最小负数乘积吗？
【在 b******v 的大作中提到】
: 嗯，我上机试了很多例子，应该没有问题
|
b******v
发帖数: 1493 | 27 也可以是正的
以a[i]结尾的lastmin是{a[j]*...*a[i],j=0,...,i}中最小的元素，可以是正也可以是负
我们需要保留这项信息，是因为当到a[i+1]时，如果a[i+1]是负数，
则以a[i+1]结尾的lastmax是max{a[i+1], lastmin[i]*a[i+1]}
【在 r****o 的大作中提到】
: 你说的最小乘积lastmin是指绝对值最大的最小负数乘积吗？
|
l******o
发帖数: 144 | 28 O(n)显然是可以做到的。和maximum sum一样，伪DP就可以了。不过maximum sum记录前
面最
大的和，这里要同时记录绝对值最大的正product和负product。Over。
饿，要是谁有我搬板凳
【在 j***n 的大作中提到】
: 饿，要是谁有我搬板凳
|
l******o
发帖数: 144 | 29 汗，原来已经有人给了解答了，刚才没看到。
可以保存如下变量：
以当前元素结尾的最大乘积lastmax，及其起始范围lastmaxstart, lastmaxend
以当前元素结尾的最小乘积lastmin, 及其起始范围lastminstart, lastminend
当前最大的乘积max, 及其起始范围maxstart, maxend
它们都初始为数组只有第一个元素时对应的值
当有一个新变量a[i]进来时
(1) 如果a[i]>0
把a[i]*lastmax与a[i]进行比较，并更新lastmax及其范围
把a[i]*lastmin与a[i]进行比较，并更新lastmin及其范围
(2) 如果a[i]<0
把a[i]*lastmin与a[i]进行比较，并更新lastmax及其范围
把a[i]*lastmax与a[i]进行比较，并更新lastmin及其范围
(3) 如果a[i]=0
lastmax, lastmin都是0
(4) 当上面三步结束时，将lastmax与max比较，并更新max及其范围
这个算法的时间复杂度显然是O(n)，空间复杂度O(1)
【在 b******v 的大作中提到】
: 可以保存如下变量：
: 以当前元素结尾的最大乘积lastmax，及其起始范围lastmaxstart, lastmaxend
: 以当前元素结尾的最小乘积lastmin, 及其起始范围lastminstart, lastminend
: 当前最大的乘积max, 及其起始范围maxstart, maxend
: 它们都初始为数组只有第一个元素时对应的值
: 当有一个新变量a[i]进来时
: (1) 如果a[i]>0
: 把a[i]*lastmax与a[i]进行比较，并更新lastmax及其范围
: 把a[i]*lastmin与a[i]进行比较，并更新lastmin及其范围
: (2) 如果a[i]<0
|
