草庐IT

c++ - 翻转卡片以获得最大金额

coder 2023-11-17 原文

给定 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";
}

最佳答案

您唯一需要找到的是您可以用连续数字形成的最小和，然后将它们翻转。在您的示例中，最后三个数字加起来为 -7，并且没有其他连续数字集的总和较低，因此翻转它们就可以了。如果最小和为非负数，则不需要翻转它们。

现在，我上面描述的是一个众所周知的算法，它被称为Kadane's algorithm ，可以在 O(n) 中求解，请注意维基百科链接显示了如何求最大值，但您可以轻松修改它以找到最小值。

关于c++ - 翻转卡片以获得最大金额，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24963978/

amp43numbersmin_ending_heresectionc++algorithm

有关c++ - 翻转卡片以获得最大金额的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 无法在 60 秒内获得稳定的 Firefox 连接 (127.0.0.1 :7055) - 2

    我使用的是Firefox版本36.0.1和Selenium-Webdrivergem版本2.45.0。我能够创建Firefox实例，但无法使用脚本继续进行进一步的操作无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)错误。有人能帮帮我吗？ 最佳答案 我遇到了同样的问题。降级到firefoxv33后一切正常。您可以找到旧版本here 关于ruby-无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)，我们在StackOverflow上找到一个类

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  6. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  7. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  8. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  9. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

    我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

  10. ruby - 我可以从 Ruby 中的系统调用中获得连续输出吗？ - 2

    当您在Ruby脚本中使用系统调用时，您可以像这样获得该命令的输出:output=`ls`putsoutput这就是thisquestion是关于。但是有没有办法显示系统调用的连续输出？例如，如果您运行此安全复制命令，以通过SSH从服务器获取文件:scpuser@someserver:remoteFile/some/local/folder/...它显示随着下载进度的连续输出。但是这个:output=`scpuser@someserver:remoteFile/some/local/folder/`putsoutput...不捕获该输出。如何从我的Ruby脚本中显示正在进行的下载进度？

随机推荐