h*******e
发帖数: 1377 | 1 大家讨论讨论。。。我想到比较naive的想法 对于不为零的一段空间， 是做个 dp[
10001][10] 10是任意取的 一个是 无穷大的，一个保存靠近 1 大于 和 小于 1 的 靠
近 0的 大于小于 负一的
，然后 相乘后update当前的index里面各个dp value~~
然后再和前面的index 相除 得到 sub array sum(double val) 然后取最大值
然后大概复杂度 O(N^2) 思路不严密
，有没有心细的版友 补充完全。 |
b******g
发帖数: 3616 | 2 看了半天没搞明白你在说哪题？没有名字叫sub Mul max的啊？你是在说Maximum
Product Subarray么？。。。。 |
h*******e
发帖数: 1377 | 3 对。。不好意思。我自己瞎给改名了。~~~
【在 b******g 的大作中提到】
: 看了半天没搞明白你在说哪题？没有名字叫sub Mul max的啊？你是在说Maximum
: Product Subarray么？。。。。
|
b******g
发帖数: 3616 | 4 这道题如果用DP的话个人觉得double和int没什么区别啊？对于每一个A[i]，dp需要已
经记录了以A[i-1]为结尾的subarray的product_min和product_max，然后推算以A[i]本身
为结尾的product_min,product_max必定在product_max*A[i], product_min*A[i]以及A
[i]三个数之间，感觉推广成double并没有影响这个逻辑，即使有(-1,1)的数？
【在 h*******e 的大作中提到】
: 对。。不好意思。我自己瞎给改名了。~~~
|
h*******e
发帖数: 1377 | 5 我想想哦
本身
及A
【在 b******g 的大作中提到】
: 这道题如果用DP的话个人觉得double和int没什么区别啊？对于每一个A[i]，dp需要已
: 经记录了以A[i-1]为结尾的subarray的product_min和product_max，然后推算以A[i]本身
: 为结尾的product_min,product_max必定在product_max*A[i], product_min*A[i]以及A
: [i]三个数之间，感觉推广成double并没有影响这个逻辑，即使有(-1,1)的数？
|
h*******e
发帖数: 1377 | 6 好的，你的做法很好，用了一个性质，2个极值 *新的数 依然是 ２个极值～～然后
不断用新数刷新极值。 依次得到最后的极值，开始我也想到这种dp但是想得不深入～
～～以
为此路不通～～。你的方法给我很大启发。
本身
及A
【在 b******g 的大作中提到】
: 这道题如果用DP的话个人觉得double和int没什么区别啊？对于每一个A[i]，dp需要已
: 经记录了以A[i-1]为结尾的subarray的product_min和product_max，然后推算以A[i]本身
: 为结尾的product_min,product_max必定在product_max*A[i], product_min*A[i]以及A
: [i]三个数之间，感觉推广成double并没有影响这个逻辑，即使有(-1,1)的数？
|
h*******e
发帖数: 1377 | 7 新技能get..3数求max 比我之前用的好～～～ |
