思路
最大连续子序列乘积和最大连续子序列和不同,这里先回忆一下最大连续子序列和的最优解结构:
最大连续子序列和
我们用sum[i]来表示以arr[i]结尾的最大连续子序列和,则状态转移方程为:
最大连续子序列乘积
考虑存在负数的情况(ps:负负会得正),因此我们用两个辅助数组,max[i]和min[i],max[i]来表示以arr[i]结尾的最大连续子序列乘积,min[i]来表示以arr[i]结尾的最小连续子序列乘积,因此状态转移方程为:
and
最后打印出最大的max[i]就行。
答疑:
--为什么要用一个数组min[]?
--因为会存在负数,min[]就是为了找到负数中最小的,这样再乘上一个负数后就变成了一个较大的正数。
分享到:
相关推荐
主要介绍了利用C语言来求最大连续子序列乘积的方法,基本的思路以外文中还附有相关ACM题目,需要的朋友可以参考下
NULL 博文链接:https://shmilyaw-hotmail-com.iteye.com/blog/1616632
有一个整数类型的nums,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数) 案例: data = [1, 2, -2, -1, 5, -4] 输出20,子序列: [-1, 5, 4] ''' nums = [1, 2, -2, -1, 5, -4] i = 3, j = 5 mul(i, j) ...
最大和连续子序列 底部的最小距离 最小硬币兑换 最低成本路径 最小分区 最小大小子阵列总和 表示数字的最小平方 最小步数为一 最低票价 最优二叉搜索树 回文分区 棒材切割 子集生成 子集总和 维特比 ...
leetcode中国数据结构和算法 ...找到最长的连续子序列 给定一个大小为 n 的数组和一个数字 k,找出出现次数超过“n/k”次的所有元素。 最多两次买卖股票的最大利润 判断一个数组是否是另一个数组的子集 找
最长递增子序列 - 最长公共子序列 - 断字问题- 组合总和 - 房屋强盗 - 房屋强盗 II - 解码方式 - 独特的路径 - 跳跃游戏—— 图形 克隆图 - 课程安排 - 太平洋大西洋水流 - 岛屿数量 - 最长连续序列 - 外星人词典 ...
最长连续递增子序列 简单的 118 帕斯卡三角形 简单的 119 帕斯卡三角形 II 简单的 217 包含重复 简单的 717 1 位和 2 位字符 简单的 695 最大岛屿面积 简单的 26 从排序数组中删除重复项 简单的 27 删除元素 简单的 ...
连续子数组和 最长递增子序列 最长公共子序列 想法 联合发现 下一个置换算法 将二维矩阵转换为一维数组 有一个公式可以将二维矩阵转换为一维数组,反之亦然 -- n * m 矩阵转换为数组 => matrix[x][y] => a[x * m + y...
最长递增子序列 - 最长公共子序列 - 断字问题- 组合总和 - 房屋强盗 - 房屋强盗 II - 解码方式 - 独特的路径 - 跳跃游戏—— 图形 克隆图 - 课程安排 - 太平洋大西洋水流 - 岛屿数量 - 最长连续序列 - 外星人词典 ...
最长递增子序列 - 最长公共子序列 - 断字问题- 组合总和 - 房屋强盗 - 房屋强盗 II - 解码方式 - 独特的路径 - 跳跃游戏—— 图形 克隆图 - 课程安排 - 太平洋大西洋水流 - 岛屿数量 - 最长连续序列 - 外星人词典 ...
最长递增子序列 - 最长公共子序列 - 断字问题- 组合总和 - 房屋强盗 - 房屋强盗 II - 解码方式 - 独特的路径 - 跳跃游戏—— 图形 克隆图 - 课程安排 - 太平洋大西洋水流 - 岛屿数量 - 最长连续序列 - 外星人词典 ...
乘积最大子序列 相交链表 打家劫舍 岛屿数量 反转链表 课程表 最大正方形 回文链表 二叉树的最近公共祖先 除自身以外数组的乘积 滑动窗口最大值 搜索二维矩阵 II 会议室 II 完全平方数 移动零 寻找重复数 二叉树的...
最大连续乘积子数组、最长递增子序列数组(不一定连续)、最大连续子数组和 从0变化到2015的最小操作次数问题、跳台阶问题 区间最小值问题(RMQ):简单动态规划法、预处理动规法 简单的0-1问题 : 只走一次的总和...
leetcode小岛出水口 leetcode training one problem on file 为了方便文档管理,项目...最长递增子序列的个数 0567. 字符串的排列 0563. Binary Tree Tilt 0547. 朋友圈 0541. 翻转字符串II 0515. 在每个树行中找最大值
最大连续数 简单的 40.08% 09 最大平均子阵列 I 简单的 72.70% 10 第三个最大数 简单的 14.80% 11 查找数组中所有消失的数字 简单的 49.05% 12 三个数的最大乘积 简单的 19.02% 13 包含重复 简单的 87.02% 14 最长...
lru缓存leetcode Leetcode-April-Challenge-2020 ...最长公共子序列 最大子平方 <第一个唯一编号> 二叉树最大路径和 <检查字符串是否是二叉树中从根到叶路径的有效序列> '< >' ==> 内未完成
最大乘积子阵列 买卖股票的最佳时机, 最长连续序列 , 树木 在二叉搜索树中搜索, 插入二叉搜索树, 最近二叉搜索树值, 最近二叉搜索树值 II , 二叉树中序遍历 二叉树先序遍历 二叉树后序遍历 二叉树级顺序遍历, ...
最大连续数 力码 72 最小高度 BST 算法专家 71 单调数组 算法专家 70 最小差异 算法专家 69 验证子序列 算法专家 68 买卖股票的最佳时机 II 第 122 章 67 移零 力码 66 快乐数,最大子数组 力码 65 单号 第 136 章 ...
最长连续序列(难) - 最大矩形(硬) - 直方图中最大的矩形(硬) - 合并间隔(中) - 插入间隔(中) - 子阵列总和等于 K (中) - 子集 II (中) - 最大岛屿面积(中) - 最大乘积子阵列(中) - 除自身以外的...