给定一个浮点数数组,任意取出数组里若干个连续的数相乘,请找出其乘积最大的子 数组。要求用动态规划求出最大的连续乘积子数组,同时输出所求子数组的开始位置 和结束位置,请用C语言实现可运行的代码
时间: 2023-07-24 21:15:30 浏览: 175
乘积最大子数组(动态规划)1
以下是C语言实现可运行的代码:
```c
#include <stdio.h>
#include <limits.h>
#define MAX_SIZE 100
int main() {
int arr[MAX_SIZE];
int n, i;
int max_product = INT_MIN;
int start_index, end_index, current_start_index;
printf("Enter the size of the array: ");
scanf("%d", &n);
printf("Enter the elements of the array: ");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int max_ending_here = 1;
int min_ending_here = 1;
for (i = 0; i < n; i++) {
if (arr[i] > 0) {
max_ending_here *= arr[i];
min_ending_here = (min_ending_here * arr[i] < 1) ? min_ending_here * arr[i] : 1;
} else if (arr[i] == 0) {
max_ending_here = 1;
min_ending_here = 1;
current_start_index = i + 1;
} else {
int temp = max_ending_here;
max_ending_here = (min_ending_here * arr[i] > 1) ? min_ending_here * arr[i] : 1;
min_ending_here = temp * arr[i];
}
if (max_ending_here > max_product) {
max_product = max_ending_here;
start_index = current_start_index;
end_index = i;
}
}
printf("The maximum product is %d\n", max_product);
printf("The subarray with maximum product is: ");
for (i = start_index; i <= end_index; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
说明:
该算法使用动态规划的思想,通过记录当前位置前的最大和最小连续乘积,来计算当前位置的最大和最小连续乘积。同时记录下乘积最大的子数组的起始和结束位置,并输出。
时间复杂度为O(n),空间复杂度为O(1)。
阅读全文