专栏首页小二的折腾日记LeetCode-53-Maximum-Subarray

LeetCode-53-Maximum-Subarray

LeetCode-53-Maximum-Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

最长子序列,又是一个动态规划的问题,关于动态规划,我们最主要的是要维护DP数组,这个问题以前还有点不理解,感觉主要的还是思想,只要知道这是一个动态规划的问题,解决动态规划的一般方法掌握了,其他的就都是细节了。

最近刷算法题,不得不想到的是以前的数学,数学是逻辑性可能更强的东西,尚且需要多做练习才行,何况算法了。当然现在慢慢的感觉就是,以前看到很多题完全没有头绪,现在很多大概是能分清是想考啥了,也会想着主动去选择相应的数据结构。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        int res=dp[0];
        for(int i=1;i<nums.size();++i){
            dp[i]=nums[i]+(dp[i-1]>0?dp[i-1]:0);
            res=max(dp[i],res);
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode-51-N-Queens

    经典的N皇后问题,重点是全排列的问题,但是这里由于N皇后的不重复行、列、斜的要求,在排列的过程中,比如从行开始排列,只能保证同行不重复,所以需要引入isVali...

    小二三不乌
  • LeetCode-34-Search-for-a-Range

    在一个排序的数组中找到出现这个值的起点和重点。很容易想到的是二分查找了。复杂度为nlog(n)。思路如下,先二分查找,找到下界,如果下界lo的值不等于targe...

    小二三不乌
  • 剑指offer-刷题总结

    分析:由于每一行都有递增的特性,我们可以采用类似二分搜索的方法。将数组分成行列来进行搜索。

    小二三不乌
  • UVALive8177 Pangu and Stones(区域赛铜牌题)

    题目来源:2017年某区域赛铜牌题。最近老师发了个题集就和室友组队模拟了一下,一开始遇到这题以为是很普通的优先队列的题目,之后看到有范围限制,立马想到了区间dp...

    ACM算法日常
  • 洛谷P1122最大子树和 树形结构计算子树和

     考虑如果子树的和为负,那么删掉它一定比不删掉它更优,用一个cut数组记录这个子树是否删去。注意这题不一定到根节点是最优的,所以要算一个子树更新一次。

    用户2965768
  • LeetCode <dp>343. Integer Break

    Given a positive integer n, break it into the sum of at least two positive integ...

    大学里的混子
  • c# winform 窗体失去焦点关闭(钩子实现)

    main函数里面写 Application.ApplicationExit += Application_ApplicationExit;

    冰封一夏
  • leetcode 27 Remove Element

    @坤的
  • JAVA通过BufferedImage进行图片的绘制,缩放,裁剪,水印等操作

    最近开发当中,通过JAVA对图片进行了很多的操作,之前很少接触这方面的知识,特此记录下来

    海加尔金鹰
  • 【POJ 1112】Team Them Up!(二分图染色+DP)

    Your task is to divide a number of persons into two teams, in such a way, that: ...

    饶文津

扫码关注云+社区

领取腾讯云代金券