搜狐编程第二题回文数组求和AC40%
设了两个变量一个left一个right，只判断了两种情况，第一种是不断加left和right代表的最小值（只能AC到30%），第二种是不断加他们代表的最大值，两种取最小，提高到了40%。其实还有其他情况就是 交叉取最大最小（用这一种情况是不是就能够AC？）。#搜狐#
2017-09-18 16:22 已编辑 中国农业大学 Java
关注
全部评论
嗯必得
Griffith University C++
用动态规划，一个数组存正向一个存逆向，求两个数组的子序列，计算出子序列中和最大的子序列，输出2倍序列和减去和最大的子序列
腾讯内推2021
北京航空航天大学 C++
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
long long L,a,sum=0;
cin>>L;
vector<long long> num;
vector<vector<long long> >M (L,vector<long long>(L,0));
for(int i=0;i<L;i++)
{
cin>>a;
num.push_back(a);
sum+=a;
}
for (int e=0;e<L;e++)
for (int s=L-1;s>=0;s--)
{
if (s<e)
{
if(num[s]==num[e]) M[s][e]=M[s+1][e-1];
else M[s][e]=min(M[s+1][e]+num[s],M[s][e-1]+num[e]);
}
}
cout<<M[0][L-1]+sum;
return 0;
}
zhang_jie
上海大学 Java
这种思路不对，应该动态规划
相关推荐