最大乘积子序列问题

给一个浮点数序列,取最大乘积子序列的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积子序列为3,0.5,8。

解法:
动态规划求解
假设数组为a[],直接利用动归来求解,考虑到可能存在负数的情况,我们用Max[i]来表示以a[i]结尾的最大连续子序列的乘积值,用Min[i]表示以a[i]结尾的最小的连续子序列的乘积值,那么状态转移方程为:
Max[i]=max{a[i], Max[i-1]a[i], Min[i-1]a[i]};
Min[i]=min{a[i], Max[i-1]a[i], Min[i-1]a[i]};
初始状态为Max[1]=Min[1]=a[1]。代码如下:

public class MaxContinuousProduct {
 
 
    // 获取数组a中,最大连续子序列的乘积
    public static double getMaxContinuousProduct(double[] a) {
        if (a.length == 0) {
            throw new IllegalArgumentException("Array a can not be empty.");
        }
 
        // min[i]表示以a[i]结尾的子序列的最小乘积
        double[] min = new double[a.length];
        // max[i]表示以a[i]结尾的子序列的最大乘积
        double[] max = new double[a.length];
        max[0] = a[0];
        min[0] = a[0];
        double maxProduct = max[0];
        for (int i = 1; i < a.length; i++) {
            max[i] = Math.max(Math.max(a[i], max[i - 1] * a[i]), min[i - 1] * a[i]);
            min[i] = Math.min(Math.min(a[i], max[i - 1] * a[i]), min[i - 1] * a[i]);
            if (max[i] > maxProduct) maxProduct = max[i];
        }
        return maxProduct;
    }
 
    public static void main(String[] args) {
        double a[] = {-2.5, 4, 0, 3, 0.5, 8, -1};
        System.out.println(getMaxContinuousProduct(a));
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,338评论 0 18
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,993评论 19 139
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,748评论 0 89
  • 也许是日子太轻, 如飘扬的柳絮。 抑或太重, 似溪流两侧的岩石, 我总有理由不写诗。 心儿,有时承载了太多的欢乐,...
    桔树上阅读 213评论 0 1