给定一个数组,要求数组内全部元素均为浮点数,任意取出数组里若干个连续的数相乘,请找出其乘积最大的子 数组。要求用动态规划求出最大的连续乘积子数组,同时输出所求子数组的开始位置和结束位置,请用C语言实现可运行的代码
时间: 2023-07-24 17:15:34 浏览: 89
乘积最大子数组(动态规划)1
好的,这是一道比较经典的动态规划问题,可以使用两个数组分别记录以当前元素为结尾的最大乘积和最小乘积,最后取最大值即可。以下是 C 语言的实现代码:
```c
#include <stdio.h>
int main() {
// 原始数组
double arr[] = {2.0, 3.0, -2.0, 4.0, -1.0, 5.0, 0.5};
int n = sizeof(arr) / sizeof(arr[0]);
// 初始化最大乘积和最小乘积数组
double max_prod[n], min_prod[n];
max_prod[0] = arr[0];
min_prod[0] = arr[0];
int start = 0, end = 0;
double max_val = arr[0];
// 动态规划求解最大乘积子数组
for (int i = 1; i < n; i++) {
double prod1 = max_prod[i-1] * arr[i];
double prod2 = min_prod[i-1] * arr[i];
max_prod[i] = fmax(arr[i], fmax(prod1, prod2));
min_prod[i] = fmin(arr[i], fmin(prod1, prod2));
if (max_prod[i] > max_val) {
max_val = max_prod[i];
start = end = i;
}
if (max_prod[i] == max_val && max_prod[i] > 0) {
end = i;
}
}
// 输出结果
printf("The maximum product is %lf.\n", max_val);
printf("The subarray starts from %d and ends at %d.\n", start, end);
return 0;
}
```
上述代码中,我们使用了 `fmax` 和 `fmin` 函数来取最大值和最小值,这是 C 语言标准库中的函数,需要在程序中包含 `math.h` 头文件。
阅读全文