【求助】只用加号或乘号对正数组各元素操作，求最大值。
假设有一个数组A，里面的元素都大于1的正整数，只采用加号或乘号，不改变数组元素的位置，如何使最后结果最大？比如：
A={2,1,1，1，1,2}那么就用加号结果为8，B={3，1，3}那么就用乘号结果为9。
小弟菜鸟，当时是这么想的：
1、只有1才会改变运算符，如果元素不是1，那么一直连乘就可以了。
2、位于数组最前面的连续的1肯定是用加号和后面第一个非1的元素连接起来的。
3、这样算下来，就只要从数组中第一个非1的元素开始考虑就行了。
以数组A为例，假设有一个函数f能够取得最后的最大值result = f(A) = f({2,1,1,1,1,2}),那么可以用递归的方法来计算，因为第一个元素为2，如果它和后面跟加号，那后面的计算和它没关系:result_1 = f({1,1,1,1,2})，如果它后面跟乘号，那么A中的第一个1必是和2相乘，则计算新的数组的值result_2 = f({2,1,1,1,2})，那最后的结果应该是
result = max(result_1, result_2),
可总觉得哪个地方不对，而且因为要比较，所以会增加一次遍历和增大运算量。不知道各位大虾有何高招？给个C版本的例子，谢谢！
[解决办法]
就是个动态规划而已，for (j=i; j>=1; --j) 是枚举最后一段连续相乘的段。
我给出完整的代码或许会比较好理解：
稍微修改了一下，增加了动态规划的路径记录，算法部分不变。
输入N，然后输入N个数字，即可输出最终算式（注意最终结果不可溢出unsigned）：
例如，输入
6
2 1 1 1 1 2
输出：
2+1+1+1+1+2=8
输入：
3
3 1 3
输出：
3*1*3=9
#include <stdio.h>#include <string.h>#define MAXN 1010unsigned ans[MAXN];int pre[MAXN], a[MAXN];bool isadd[MAXN];int n;int main(){ int i,j; unsigned k; ans[0] = 0; while (scanf("%d", &n) != EOF){ for (i=1; i<=n; ++i) scanf("%d", a+i); memset(isadd, false, sizeof isadd); for (i=1; i<=n; ++i){ ans[i] = 0; k = 1; for (j=i; j>=1; --j){ k *= a[j]; // 计算连乘 if (k + ans[j-1] > ans[i]){ ans[i] = k + ans[j-1]; pre[i] = j-1; } } } // 根据pre倒推出算式 for (i=pre[n]; i; i=pre[i]) isadd[i] = true; for (i=1; i<n; ++i) printf("%d%c", a[i], isadd[i]?'+':'*'); printf("%d=%u\n", a[n], ans[n]); }}
[解决办法]
#include <iostream>using namespace std;#define MIN -1class Sum{private: int *result;//动态规划表格,result[n]表示1....n做加乘综合运算后的最大值 int *path;//在动态规划递推过程中记录加号出现位置 int *arr;//存放num个数字 int num;//数字序列的长度public: //构造函数 Sum(int num)//num个数字 { this->num=num; result=new int[num+1];//用数组下标的1到n path=new int[num+1];//记录路径也只用1到n arr=new int[num+1];//开辟数组存放数字序列,只用1到n } //输入数字序列 void input() { for(int i=1;i<=num;i++) { cin>>arr[i]; } } //动态规划求解 ,公式: result[n]=max { (x[k]*x[k+1]*x[k+2]*....x[n])+result[k-1] } ，k取1....n void maxResult() { //初始化reslut[0]=0，即0个数据的最大值为0,初始化result[1]=arr[1],即前1个数据的最大值为本身 result[0]=0; result[1]=arr[1]; path[1]=1; //递推求解,最终result[n]表示前n个数的最大值 int localSum; for(int i=2;i<=num;i++) { result[i]=MIN; for(int k=i;k>=1;k--) { localSum=1; int temp=k; //求x[k]*x[k+1]*.....x[i] while(temp<=i) { localSum*=arr[temp++]; } //求x[k]*x[k+1]*.....x[i]+result[k-1] localSum+=result[k-1]; //记录k取不同值时所能达到的最大值,并记录断点path[i] if(localSum>result[i]) { result[i]=localSum; path[i]=k; } } } } //打印结果 void display() { cout<<"最大*，+结果："<<result[num]<<endl; printPath(num); } //递归打印整个公式 void printPath(int n) { if(path[n]==1) { int j=1; while(j<=n) { cout<<arr[j]; if(j<n) { cout<<"*"; } ++j; } return; } printPath(path[n]-1); cout<<"+"; int i=path[n]; while(i<=n) { cout<<arr[i]; if(i<n) { cout<<"*"; } ++i; } }};void main(){ Sum sum(6); // 2 1 1 1 1 2 sum.input(); sum.maxResult(); sum.display();}
[解决办法]
#10的代码已经相当好了，我再唠叨两句。
1> 先对输入的数组进行遍历，统计连续1的个数，统计连续非1的乘积，形成如下形式
S0个1，乘积1，S1个1，乘积2，S2个1，乘积3，……Sk个1
其中S0或Sk可能为0
2> S0和Sk必然是相加的关系
3> S1——S(k-1)这些部分，作为相加部分就是本身，作为相乘部分就是1
4> 对k个乘积和k-1个"连续1”做动归
这样，如果题目给10000个1，那么这个算法可以用O(N)的时间算出。