一筐愿望 2013-11-14 05:48 采纳率: 60%
浏览 1164

算法:求子数组的最大乘积

算法概述:
编程之美和其他教材上都有介绍过这种算法

通过空间换时间来降低时间复杂度,设array[]为初始数组
s[i]表示数组前i个元素的乘积,其中1<=i<=N,s[0]=1;
t[i]表示数组后(N-i)个元素的乘积,其中1<=i<=N,t[N+1]=1。
设p[i]为数组除第i个元素外,其他N-1个元素的乘积。
p[i]=s[i-1]*t[i+1]
由于只需要从头到尾和从尾到头扫描数组两次即可得到s[]和t[],进而线性时间就可以得到p[],所以很容易就可以得到p[]的最大值,总的时间复杂度为O(N)

下面开始计算

有值为1、2、4、3的数组
i=1时,左侧没有值,右侧2、4、3的乘积为24,最后结果为24(最大值)
i=2时,左侧值为1,右侧值为4、3的乘积为24,最后结果为12
i=4时,左侧值为1、2,乘积为2,右侧值为3,最后结果为6
i=3时,左侧值为1、2、4,乘积为8,右侧没有值,最后结果为8
最后得到子数组的最大积为24

如果数组中元素均为正整数的话,那么上面的算法我能理解,毕竟乘法位数越多结果越大呗,数组中有五个元素,那求剩下四个元素所能组合出的乘积最大值就可以了,但是如果是负数这个算法不就不成立了吗?

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥50 永磁型步进电机PID算法
    • ¥15 sqlite 附加(attach database)加密数据库时,返回26是什么原因呢?
    • ¥88 找成都本地经验丰富懂小程序开发的技术大咖
    • ¥15 如何处理复杂数据表格的除法运算
    • ¥15 如何用stc8h1k08的片子做485数据透传的功能?(关键词-串口)
    • ¥15 有兄弟姐妹会用word插图功能制作类似citespace的图片吗?
    • ¥200 uniapp长期运行卡死问题解决
    • ¥15 latex怎么处理论文引理引用参考文献
    • ¥15 请教:如何用postman调用本地虚拟机区块链接上的合约?
    • ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?