给定N张牌,如果第i张牌在其正面有数字x,那么它将在背面具有-x并且只能进行一次操作,只能以连续顺序翻转任意数量的牌一次.
现在我们需要以这样的方式翻转卡片,即卡片上面的数量总和最大.
示例:如果N = 5且cards []为{-2,3,-1,-4,-2},那么这里的答案是8,因为我们可以翻转最后3张卡来获得配置{-2,3,1,4 ,2}总和为8.
我的方法:
为每个第i个位置寻找每种可能的方式作为起始位置并找到最大值.但是他们对这个问题有更好的解决方案吗？
我的密码:直到现在还没有找到问题
#include<bits/stdc++.h>
using namespace std;
int solve(std::vector<int> const & numbers)
{
int min_so_far = numbers[0], min_ending_here = numbers[0];
size_t begin = 0;
size_t begin_temp = 0;
size_t end = 0;
for(size_t i = 1; i < numbers.size(); i++)
{
if(min_ending_here > 0)
{
min_ending_here = numbers[i];
begin_temp = i;
}
else
{
min_ending_here += numbers[i];
}
if(min_ending_here <= min_so_far )
{
min_so_far = min_ending_here;
begin = begin_temp;
end = i;
}
}
int sum=0;
for(int i=0;i<begin;i++){
sum+=numbers[i];
}
for(int i=begin;i<=end;i++){
sum-=numbers[i];
}
for(int i=end+1;i<numbers.size();i++){
sum+=numbers[i];
}
return sum;
}
int main(){
int n;
cin>>n;
vector<int> arr;
for(int i=0;i<n;i++){
int x;
cin>>x;
arr.push_back(x);
}
cout<<solve(arr)<<"\n";
}