- 题目来源：小米手机2013年校园招聘笔试题
- 题目描述：
-
给定一个浮点数序列（可能有正数、0和负数），求出一个最大的连续子序列乘积。
- 输入：
-
输入可能包含多个测试样例。
每个测试样例的第一行仅包含正整数 n（n<=100000），表示浮点数序列的个数。
第二行输入n个浮点数用空格分隔。
输入数据保证所有数字乘积在双精度浮点数表示的范围内。
- 输出：
-
对应每个测试案例，输出序列中最大的连续子序列乘积，若乘积为浮点数请保留2位小数，如果最大乘积为负数，输出-1。
- 样例输入：
-
7
-2.5 4 0 3 0.5 8 -1
5
-3.2 5 -1.6 1 2.5
5
-1.1 2.2 -1.1 3.3 -1.1
- 样例输出：
-
12
64
8.78 思路：
这道题目和最大连续子字段和是类似的，也是用dp，只是对于每个数（假设该数是第i个数），我们要存放两个状态，一个是前i个数中包含第i个数的连续子段乘积的最大正数，一个是前i个数中包含第i个数的连续子段乘积的最小负数。假设data[i]存放第i个数，ans[i][0]和ans[i][1]分别存放连续子段乘积的最大正数和最小负数。
状态转移具体可以分情况讨论：- 当i = 1时
如果data[i] >= 0，则ans[1][0] = data[1], ans[1][1] = FMAX (FMAX = -0.001, 表示最大负数)
如果data[i] < 0，则ans[1][0] = ZMIN, ans[1][1] = data[1] (ZMIN = 0.001, 表示最小正数) - 当1 < i <= n 时
（1）情况一：如果data[i] >= 0 - 如果ans[i - 1][0] == ZMIN 或者 data[i] * ans[i - 1][0] <= data[i]
ans[i][0] = data[i] - 如果data[i] * ans[i - 1][0] > data[i]
ans[i][0] = data[i] * ans[i - 1][0] - 如果ans[i - 1][1] == FMAX
ans[i][1] = FMAX - 如果ans[i - 1][1] > FMAX
ans[i][1] = ans[i - 1][1] * data[i]
（2）情况二：如果data[i] < 0
- 如果ans[i - 1][0] == ZMIN 或者 data[i] * ans[i - 1][0] <= data[i]
ans[i][1] = data[i] - 如果data[i] * ans[i - 1][0] > data[i]
ans[i][1] = data[i] * ans[i - 1][0] - 如果ans[i - 1][1] == FMAX
ans[i][0] = ZMIN - 如果ans[i - 1][1] > FMAX
ans[i][0] = ans[i - 1][1] * data[i]
这道题需要注意的是浮点数为0的判断，悲剧自己在这上面wa了好几次！！！看来自己对浮点数的理解还是比较模糊！！
// 1501.cpp : 定义控制台应用程序的入口点。
// #include <stdio.h>
#include <math.h> int n;
double data[ + ];
double ans[ + ][];
double max; #define JD 0.0000001 #define FMAX -0.001
#define ZMIN 0.001 int flag; int main(void)
{
int i; // freopen("in.txt", "r", stdin);
while (scanf("%d", &n) != EOF)
{
flag = ;
for (i = ; i <= n; i ++)
{
scanf("%lf", &data[i]);
if (fabs(data[i]) < JD)
flag = ;
}
if (data[] >= )
{
ans[][] = data[];
ans[][] = FMAX;
}
else
{
ans[][] = ZMIN;
ans[][] = data[];
}
for (i = ; i <= n; i ++)
if (data[i] >= )
{
if (fabs(ans[i - ][] - ZMIN) < JD || data[i] * ans[i - ][] < data[i])
ans[i][] = data[i];
else
ans[i][] = data[i] * ans[i - ][];
if (fabs(ans[i - ][] - FMAX) < JD)
ans[i][] = FMAX;
else
ans[i][] = ans[i - ][] * data[i];
}
else
{
if (fabs(ans[i - ][] - ZMIN) < JD || data[i] * ans[i - ][] > data[i])
ans[i][] = data[i];
else
ans[i][] = data[i] * ans[i - ][];
if (fabs(ans[i - ][] - FMAX) < JD)
ans[i][] = ZMIN;
else
ans[i][] = ans[i - ][] * data[i];
}
max = ans[][];
for (i = ; i <= n; i ++)
if (ans[i][] > max)
max = ans[i][];
if (max > ZMIN)
{
if (fabs(max - (int)max) <= JD)
printf("%d\n", (int)max);
else
printf("%.2f\n", max);
}
else if (fabs(max) <= ZMIN && flag)
printf("0\n");
else
printf("-1\n");
}
return ;
} - 当i = 1时