最大连续乘积子数组

一、题目

//给定浮点数数组,任意取出数组中的若干个连续的数相乘,请找出最大的子数组。 //比如:{-2.5,4,0,3,0.5,8,-1},则取出的最大乘积子数组为{3,0.5,8},也就是3,0.5,8这三个数是连续的且乘积是最大的。

二、方法一:暴力求解(O(n^2))

static double a[] = new double[] { -2.5, 4, 0, 3, 0.5, 8, -1 }; static double maxResult; //暴力求解 public static void getResult1() { for (int i = 0; i < a.length; i++) { double x = 1; for (int j = i; j < a.length; j++) { x *= a[j]; if (x > maxResult) { maxResult = x; } } } System.out.println(maxResult); }

三、方法二:动态规划(O(n))

因为数组中包括负数。 设maxEnd表示以a[i]结尾的最大连续子数组的乘积值。 设minEnd表示以a[i]结尾的最小连续子数组的乘积值。 可得到状态转移方程: 1、maxEnd=max{ max{maxEnd*a[i]，minEnd*a[i]}，a[i]); ( 意思是:以a[i]结尾的最大(小)连续子数组的乘积值是：A,B,C中的最大值。 A：以a[i-1]结尾的最大连续子数组的乘积值 B：以a[i-1]结尾的最小连续子数组的乘积值 C：a[i]自身的值 ) 2、minEnd=min{ min{minEnd*a[i]，minEnd*a[i]}，a[i]}; 由状态转移方程可以写出代码:

static double a[] = new double[] { -2.5, 4, 0, 3, 0.5, 8, -1 }; static double maxResult; static double maxEnd; static double minEnd; public static void main(String[] args) { getResult2(); } /** * 动态规划法 */ public static void getResult2() { for (int i = 1; i < a.length; i++) { double end1 = maxEnd * a[i]; double end2 = minEnd * a[i]; maxEnd = Math.max(Math.max(end1, end2), a[i]); minEnd = Math.min(Math.min(end1, end2), a[i]); maxResult = Math.max(maxResult, maxEnd); } System.out.println(maxResult); }

We often hear of people breaking down from overwork，but in nine cases out of ten they are really suffering from worry or anxiety.