c语言给你-一个整数数组a,请编程输出-一个子数组,要求子数组元素乘积最大。需给出

子数组的起始位置和结束位置。

这道题可以采用动态规划的思想解决。

我们定义两个数组：maxVal和minVal，分别存储以当前元素为结尾的子数组的最大乘积和最小乘积。那么转移方程如下：

maxVal[i] = max(maxVal[i-1]*a[i], minVal[i-1]*a[i], a[i])
minVal[i] = min(maxVal[i-1]*a[i], minVal[i-1]*a[i], a[i])

其中a[i]表示当前元素的值。

最终的结果即为maxVal数组中的最大值。

完整的代码如下：

#include <stdio.h>

int main() {
int a[] = {2, -3, 4, -5, 0, 1};
int n = sizeof(a) / sizeof(int); // 数组长度
int start = 0, end = 0; // 记录最大子数组的起始位置和结束位置
int maxVal = a[0], minVal = a[0], ans = a[0]; // 初始化
for (int i = 1; i < n; i++) {
int tmpMax = maxVal, tmpMin = minVal;
maxVal = max(tmpMax * a[i], tmpMin * a[i], a[i]);
minVal = min(tmpMax * a[i], tmpMin * a[i], a[i]);
if (maxVal > ans) {
ans = maxVal;
end = i;
}
}
// 找到起始位置
for (int i = end; i >= 0; i--) {
if (a[i] == 0) {
start = i + 1;
break;
}
}
printf("子数组的起始位置：%d，结束位置：%d，最大乘积：%d", start, end, ans);
return 0;
}

int max(int a, int b, int c) {
int maxVal = a > b ? a : b;
return maxVal > c ? maxVal : c;
}

int min(int a, int b, int c) {
int minVal = a < b ? a : b;
return minVal < c ? minVal : c;
}