正文

leetcode刷题笔记-动态规划-day5(代码片段)

ΘLLΘ  ΘLLΘ  2022-12-19  252

关键词：

文章目录

LeetCode刷题笔记-动态规划-day5

LeetCode刷题笔记-动态规划-day5

53. 最大子数组和

1.题目

原题链接：53. 最大子数组和

2.解题思路

算法：前缀和

我们用一个sum变量表示遍历到当前位置数组的前缀和
用minn变量表示遍历到当前位置，前面所有位置前缀和的最小值
遍历过程中答案需要更新，应该等于：res=max(res,sum-minn);

3.代码

class Solution 
public:
    int maxSubArray(vector<int>& a) 
        int res=-1e9;
        int sum=0,minn=1e9;
        for(int i=0;i<a.size();i++)
            minn=min(minn,sum);
            sum+=a[i];
            res=max(res,sum-minn);
        
        return res;
    
;

918. 环形子数组的最大和

1.题目

原题链接：918. 环形子数组的最大和

2.解题思路

算法：单调栈+前缀和

因为这是一个环形的数组，一般我们在做环形的题目的时候，都会将其变成长度为环形长度两部的数组，只需要维护中间一段长度为n的数组，这样就等价于环形问题。
对转换的数组求前缀和
然后维护一个单调队列，这里用deque维护，队头维护的是最小前缀和的下标
每次更新需要检查队内元素是否多余n个，多余的话队头元素出队
每次更新答案： res=max(res,s[i]-s[q.front()]);
每次入队需要将当前队尾前缀和大于当前入队下标前缀和的元素删除
每次遍历结束，入队

3.代码

class Solution 
public:
    int maxSubarraySumCircular(vector<int>& a) 
            int n=a.size();
            vector<int> s(2*n+1);
            for(int i=1;i<=2*n;i++)
                s[i]+=s[i-1]+a[(i-1)%n];
            
            int res=-1e9;
            deque<int> q;
            q.push_back(0);
            for(int i=1;i<=2*n;i++)
                while(q.size()&&i-q.front()>n) q.pop_front();
                res=max(res,s[i]-s[q.front()]);
                while(q.size()&&s[i]<=s[q.back()]) q.pop_back();
                q.push_back(i);
            
            return res;
    
;

leetcode刷题笔记-动态规划-day6(代码片段)

文章目录LeetCode刷题笔记-动态规划-day6152.乘积最大子数组1.题目2.解题思路3.代码1567.乘积为正数的最长子数组长度1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day6152.乘积最大子数组1.题目原题链接：152.乘积最大子数组2.解... 查看详情

leetcode刷题笔记-动态规划-day6(代码片段)

leetcode刷题笔记-动态规划-day7(代码片段)

文章目录LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目2.解题思路3.代码121.买卖股票的最佳时机1.题目2.解题思路3.代码122.买卖股票的最佳时机II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目原... 查看详情

leetcode刷题笔记-动态规划-day7(代码片段)

leetcode刷题笔记-动态规划-day1(代码片段)

文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接：509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情

leetcode刷题笔记-动态规划-day1(代码片段)

leetcode刷题笔记-动态规划-day3(代码片段)

文章目录LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目2.解题思路3.代码213.打家劫舍II1.题目2.解题思路3.代码740.删除并获得点数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目原题链接：198.打家劫舍2.... 查看详情

leetcode刷题笔记-动态规划-day3(代码片段)

leetcode刷题笔记-动态规划-day4(代码片段)

文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接：55.跳跃游戏2.解题思路算法：贪心我们用变量j表示从前... 查看详情

leetcode刷题笔记-动态规划-day4(代码片段)

leetcode刷题笔记-动态规划-day2(代码片段)

文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接：70.爬楼梯2.解题思路算法：递推定义数组f[i]表示... 查看详情

leetcode刷题笔记-动态规划-day2(代码片段)

leetcode刷题笔记——动态规划(代码片段)

动态规划的⼀般流程就是三步：暴⼒的递归解法->带备忘录的递归解法->迭代的动态规划解法。就思考流程来说，就分为⼀下⼏步：找到状态和选择->明确dp数组/函数的定义->寻找状态之间的关系。明确dp[i][j]... 查看详情

leetcode刷题笔记-数据结构-day5(代码片段)

文章目录LeetCode刷题笔记-数据结构-day5334.递增的三元子序列1.题目描述2.解题思路3.代码238.除自身以外数组的乘积1.题目描述2.解题思路3.代码560.和为K的子数组1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day5334.递增的三元... 查看详情

leetcode刷题笔记-动态规划-day1(代码片段)

leetcode刷题分类笔记(代码片段)

leetcode刷题分类笔记202204130.常规操作1.链表83.删除排序链表中的重复元素203.移除链表元素2.二叉树leetcode108.将有序数组转换为二叉搜索树111.二叉树的最小深度113.路径总和II543.二叉树的直径3.动态规划45.跳跃游戏II96.不同的二叉搜... 查看详情

leetcode刷题笔记-动态规划-day2(代码片段)

leetcode之动态规划刷题总结8(代码片段)

leetcode之动态规划刷题总结8动态规划（英语：Dynamicprogramming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法... 查看详情