目录

题干

题面描述

输入

输出

示例输入

示例输出

分析

代码

运行结果

---

题干

题面描述

大贤者福尔的数学研究成绩斐然，影响力越来越大，也有很多人向他请教。最近，有人咨询他一个问题。给定若干个整数S = {S1, S2, ..., Sn}，其中若干个连续的数的最大乘积是多少？

福尔觉得这个问题太简单，他想把这个问题作为对你的考验，你能够解出来吗？

输入

输入数据有若干行，每行包含N(1 <= N <= 18)个空格分隔的整数SS，每个整数Si​的范围为−10 <= Si​ <= 10。

输出

对每行输入数据，先在单独的行中输出如Case x: ans from-to的测试样例信息，xx为测试样例编号，从1开始，ans为满足要求的最大乘积及对应的起止范围，若有多个连续序列满足条件，选择范围最小的序列，若存在多个相同范围的序列，取起始位置最小的序列，起始位置从0开始计算。

示例输入

1
1 2
-1 1
-1 0 1
1 1 9

示例输出

Case 1: 1 0-0
Case 2: 2 1-1
Case 3: 1 1-1
Case 4: 1 2-2
Case 5: 9 2-2

分析

本题由动态规划经典例题 "乘积最大子数组" 改编

LeetCode 152. 乘积最大子数组_Corux的博客-CSDN博客

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;typedef long long Num;
typedef pair<Num, int> pro;
vector<pro> S(18), maxPro(18), minPro(18);const pro& get_max(const pro& A, const pro& B) {if (A.first > B.first) return A;else if (A.first < B.first) return B;else if (A.second > B.second) return A;else return B;
}const pro& get_min(const pro& A, const pro& B) {if (A.first < B.first) return A;else if (A.first > B.first) return B;else if (A.second > B.second) return A;else return B;
}int main() {Num count = 0;while (cin.peek() != EOF) {cout << "Case " << ++count << ": ";int End = 0;while (cin.peek() != '\n') {int tmp;	cin >> tmp;S[End] = { tmp, End };++End;}cin.get();maxPro[0] = minPro[0] = S[0];pro max_pro = S[0];	int to = 0;for (int i = 1; i < End; ++i) {pro xP({ maxPro[i - 1].first * S[i].first, maxPro[i - 1].second });pro iP({ minPro[i - 1].first * S[i].first, minPro[i - 1].second });maxPro[i] = get_max(get_max(xP, iP), S[i]);minPro[i] = get_min(get_min(xP, iP), S[i]);int l = to - max_pro.second, _l = i - maxPro[i].second;if ((maxPro[i].first > max_pro.first) ||((maxPro[i].first == max_pro.first) &&((_l < l) || (_l == l && maxPro[i].second < max_pro.second)))) {max_pro = maxPro[i];to = i;}}cout << max_pro.first << " " << max_pro.second << "-" << to << endl;}
}

运行结果