UVa 787 Maximum Sub‑sequence Product

题目描述给定一个整数序列要求找出其中非空连续子序列的最大乘积。序列中的每个数最多555位序列长度最多100100100。输入包含多个序列每个序列以数字-999999结束该数字不属于序列。输出每个序列的最大子序列乘积。输入格式输入文件包含多组序列。每个序列可能跨越多行以-999999结束。每个整数最多555位序列长度最多100100100。输出格式对于每个序列输出一行包含最大子序列乘积整数无前导零。样例输入1 2 3 -999999 -5 -2 2 -30 -999999 -8 -999999 -1 0 -2 -999999样例输出6 120 -8 0题目分析求连续子序列的最大乘积经典解法为动态规划。由于乘积可能非常大100100100个999999999999999的乘积远超646464位整数范围必须使用高精度大整数运算。对于每个位置iii维护两个值以iii结尾的子序列的最大乘积max_cur\textit{max\_cur}max_cur和最小乘积min_cur\textit{min\_cur}min_cur。转移时考虑当前元素xxx候选值有三个xxx本身、max_cur×x\textit{max\_cur} \times xmax_cur×x、min_cur×x\textit{min\_cur} \times xmin_cur×x。更新max_cur\textit{max\_cur}max_cur为三者中的最大值min_cur\textit{min\_cur}min_cur为三者中的最小值。全局最大乘积max_global\textit{max\_global}max_global在所有max_cur\textit{max\_cur}max_cur中取最大。由于xxx可为负数维护最小值是为了后续负数乘以负数变为正数。解题思路实现步骤确定如下步骤1\texttt{1}1. 定义大整数结构体BigInteger\texttt{BigInteger}BigInteger包含符号sign\textit{sign}sign111为正−1-1−1为负和数字字符串digits\textit{digits}digits。实现乘法运算使用字符串模拟十进制乘法并处理符号。实现比较运算符和max⁡\maxmax、min⁡\minmin辅助函数比较规则先比较符号再比较绝对值大小。步骤2\texttt{2}2. 读取输入遇到-999999表示一个序列结束。对每个读入的整数将其转换为BigInteger\texttt{BigInteger}BigInteger并存入数组。当遇到结束标志时调用maximum_product\textit{maximum\_product}maximum_product函数计算最大乘积并输出。步骤3\texttt{3}3.maximum_product\textit{maximum\_product}maximum_product函数初始化max_cur\textit{max\_cur}max_cur、min_cur\textit{min\_cur}min_cur、max_global\textit{max\_global}max_global为第一个元素。从第二个元素开始遍历计算三个候选乘积更新max_cur\textit{max\_cur}max_cur和min_cur\textit{min\_cur}min_cur并更新max_global\textit{max\_global}max_global。最终返回max_global\textit{max\_global}max_global。步骤4\texttt{4}4. 输出时若符号为负则先输出-再输出数字字符串。注意乘积可能为零此时符号应为正且数字为0。该算法时间复杂度O(n×L2)O(n \times L^2)O(n×L2)其中LLL为乘积的位数最多约500500500位n≤100n \le 100n≤100完全可行。空间复杂度O(L)O(L)O(L)。代码实现// Maximum Sub-sequence Product// UVa ID: 787// Verdict: Accepted// Submission Date: 2016-12-01// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 十进制下的四则运算。constintBASE10;structBigInteger{intsign;string digits;booloperator(BigInteger x)const{if(sign*x.sign-1)returnsign-1;{boolbiggerfalse;if(digits.length()!x.digits.length())biggerdigits.length()x.digits.length();else{for(inti0;idigits.length();i)if(digits[i]!x.digits[i]){biggerdigits[i]x.digits[i];break;}}if(sign-1)returnbigger;elsereturn!bigger;}}};// 移除计算结果的前导0。voidzeroJustify(stringnumber){while(number.front()0number.length()1)number.erase(number.begin());}// 两个非负整数的乘法。BigIntegermultiplicate(BigIntegernumber1,BigIntegernumber2){// 预分配存储空间。stringnumber3(number1.digits.length()number2.digits.length(),0);// 从最低位开始相乘。intlength1number1.digits.length()-1,length2number2.digits.length()-1;for(intilength1;i0;i--)for(intjlength2;j0;j--){intknumber3.length()-1-(length1-ilength2-j);number3[k](number2.digits[j]-0)*(number1.digits[i]-0);number3[k-1]number3[k]/BASE;number3[k]%BASE;}// 将数值转换为对应的数字字符。for(inti0;inumber3.length();i)number3[i]0;zeroJustify(number3);intsignnumber1.sign*number2.sign;if(number30)sign1;return(BigInteger){sign,number3};}BigIntegermaximum_product(BigInteger data[],intn){BigInteger maximumdata[0],max_currentdata[0],min_currentdata[0];for(inti1;in;i){BigInteger next_maxmultiplicate(max_current,data[i]);BigInteger next_minmultiplicate(min_current,data[i]);max_currentmax(data[i],max(next_max,next_min));min_currentmin(data[i],min(next_max,next_min));maximummax(maximum,max_current);}returnmaximum;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn0;BigInteger data[110];string number;while(cinnumber){if(number-999999){BigInteger resultmaximum_product(data,n);if(result.sign-1)cout-;coutresult.digits\n;n0;}else{intsign1;if(number.front()-){sign-1;number.erase(number.begin());}data[n](BigInteger){sign,number};}}return0;}总结本题通过动态规划维护以当前元素结尾的最大和最小乘积解决了含负数的最大连续子序列乘积问题。由于乘积可能极大使用高精度大整数实现乘法与比较。转移时考虑三个候选值确保负数相乘的正确性。该算法时间复杂度O(n⋅L2)O(n \cdot L^2)O(n⋅L2)空间复杂度O(L)O(L)O(L)适用于n≤100n \le 100n≤100的规模。高精度运算的实现采用十进制字符串模拟结构清晰易于扩展。