中级光能
题目描述 Description
现在给出一个长度为n的由数字组成的字符串，试往每两个数字之间添加+、-、*，可以通过()任意改变运算优先级，求出这个式子能得到的最大值。
输入描述 Input Description
一行，一个数字串s
输出描述 Output Description
一个整数，表示能得到的最大值
样例输入 Sample Input
232
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
2 * 3 * 2
n<10
80分代码:
#include<iostream>
using namespace std;
int n,a[1005],cnt;
int maxcross(int l,int r){
int mid=(l+r)/2;
int s1=0,s2=0,maxl=-100000,maxr=-100000;
for(int i=mid;i>=l;i--){
s1=max(s1+a[i],max(s1-a[i],s1*a[i]));
maxl=max(maxl,s1);
}
for(int i=mid+1;i<=r;i++){
s2=max(s2+a[i],max(s2-a[i],s2*a[i]));
maxr=max(maxr,s2);
}
return maxl*maxr;
}
int f(int l,int r){
if(l==r)return a[l];
int mid=(l+r)/2,maxl=f(l,mid),minl=f(mid+1,r),maxt=maxcross(l,r);
return max(maxl,max(minl,maxt));
}
int t;
int main(){
cin>>n;
while(n){
a[++cnt]=n%10;
n/=10;
t+=a[cnt];
}
if(t>f(1,cnt)){
cout<<t;
}
else{
cout<<f(1,cnt);
}
return 0;
}
