给一个浮点数序列,取最大乘积子序列的值,例如 -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));
}
}