首页 > 编程语言 >最大子数组之和完成心得--贪心算法的应用

最大子数组之和完成心得--贪心算法的应用

时间:2022-10-28 18:39:39浏览次数:47  
标签:pre nums -- maxAns 算法 数组 心得 贪心

	int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;

使用贪心算法,在导入的数组中,初始化初始值为nums[0]。
在x移动后,如果x所在位置的前面的值相加为负数,则丢弃,如果为正则相加
在取得过程中的最大值,便是子数组的最大和

标签:pre,nums,--,maxAns,算法,数组,心得,贪心
From: https://www.cnblogs.com/maoino/p/16837033.html

相关文章

  • SAP 物料凭证 冲销对应关系
     执行事务码 MBSM,可以输入对应的条件   查询结果   对应的字段SELECT   mblnr,   mjahr,   zeile,   smbln,   sjahr,   sm......
  • 异步发送mq消息sdk源码分析
    1.异步发送API接口publicvoidsend(finalMessagemessage,finalAsyncSendCallbackcallback)2.实现类分析publicvoidsend(finalMessagemessage,finalAsyncS......
  • git 2022-10-28
    很长时间没有使用git了故重新写一遍关于git操作相关的随笔 1:我用vs做了一个基于qt的空窗口,并成功运行->现在我要把它上传到仓库(gitinit->gitadd.......
  • python 中实现向列表的最后一位或者最后两位之前插入元素
     001、>>>list1##测试列表[1,2,3,4,5]>>>list1.insert(-1,"xxx")##在列表最后以为之前插入数据>>>list1[1,2,3,4,'......
  • 【AGC023F】01 on Tree(树上一类全序问题)
    显然如果没有树的限制,我们优先选\(0\),然后选\(1\)。如果有了树的限制,我们考虑下面这么一种贪心方法:假设当前能够选的点的集合为\(S\)(初始时\(S\)只包含根),然后选出\(......
  • 【AGC013D】Piling Up(神奇的dp)
    考场上用了一种奇怪的做法,不知道为什么就对了,考完后仔细想才想明白。很巧妙的一种dp方式。首先发现每次操作是拿一个球、放两个球、再拿一个球,总球数不变,所以有\(\tex......
  • 【AGC010E】Rearranging(博弈,图论,拓扑排序)
    考场上想了很久才想到做法,然后考完后又想了很久,加上看了一下一些大佬的博客和Atcoder的官方题解,才完整地证明了整个做法的正确性。综合了一下,在这里详细阐述:首先发现如......
  • 【AGC005D】_K Perm Counting(容斥,二分图,计数dp)
    首先正面做不太好做,考虑容斥。设\(f(m)\)表示排列中至少有\(m\)处\(|P_i-i|=k\)的方案数。那么答案就是\(\sum\limits_{i=0}^n(-1)^if(i)\)。原题可以看成一个二......
  • 【AGC003F】Fraction of Fractal(dp,矩阵快速幂)
    先说一下下文会用到的定义或称呼的意思:称单位分形为题目给出的\(1\)级分形。称一种分形左右联通,则说明将两个这种分形左右放在一起时,至少有一个连通块是跨越这两个......
  • 【ABC196F】Substring 2(多项式乘法)
    我竟然能在AT当场做出F题!哦,是ABC啊,没事了。以下的字符串均从\(1\)开始记位。以下设\(S_i\)表示字符串\(S\)的第\(i\)位,\(S(l,r)\)表示字符串\(S\)的第......