发帖
雷达卡
http://blog.csdn.net/martin_liang/article/details/40273547
********************************************************************************************
上面帖子关于最大乘积点的公式更清楚一些。例子还是用上一篇的，我在原序列前加了两个0，比较方便用公式。
实现代码:
proc iml;
a={0 0 -2.5 4 0 3 0.5 8 -1};
max=j(1,9,0);
min=j(1,9,0);
do i=3 to ncol(a);
max=max(a,a*max[i-1],a*min[i-1]);
min=min(a,a*max[i-1],a*min[i-1]);
end;
print a;
print max;
print min;
quit;
*******************************************************************************************
结果：
a
00-2.54030.58-1
max
0004031.5120
min
00-2.5-100000-12
*******************************************************************************************
心得:
1 空间换时间。动态规划在求解过程中保留了中间结果，所以用额外的存储空间换来了计算时间的节约(需要时不用再算)
ex:
攀岩：动态规划是顺着锚点一步步向上爬，普通人就可以轻易做到。蛮力解(穷举)则需要武林高手，不能借助锚点，只能一步到顶。所以如果攀岩的高度比较高，蛮力的方法很快就会变得不可行。
2 完全的考虑。动态规划之所以可以实行源于每一步都能找到最好的锚点，而这取决于对问题的解析。比如这串数字问题，其实本质上应当理解为每一步存在三种可能:
i.正负变换(正数和负数)
ii.放大缩小(abs(乘数) > 1 或 <1)
iii.归零
要保存max和min序列是因为存在正负号变向的可能，保留“振幅”的极端情况(i条件)。
ex:
客户行为:假设一串数字记录某用户对产品的使用情况，正数代表用户的感觉是好的，负数则相反。归零表示新用户或者用户的行为在经历了一系列后相当于新用户。求最大子串的问题就等价成为用户某段时间内对产品最满意的问题。
连续的正数表示用户的感觉持续为正(但是可能放大或缩小),反转有可能是因为某件时间，用户的态度发生180转变。
因此这个例子如果泛化可以用来理解用户行为。
京公网安备 11010802022788号
