静寂旮旯

题解

/ 注册

全部文章 / 题解（共43篇）

题解 | #最大子矩阵#

关于暴力的解题思路没什么可说的，无非是搜索模式的不同。此题应该属于线性dp的一种变化，对于一位数组的连续子数组最大和的状态表达式是dp[i]=max(dp[i−1]+v[i],v[i])dp[i] = max(dp[i-1]+v[i],v[i])dp[i]=max(dp[i−1]+v[i],v[...

C++ 动态规划

2022-04-11

5 360

题解 | #环形数组的连续子数组最大和#

解题思路1：看似明显的线性dp 但是对于每一个点作为起点做dp无疑是暴力解法。时间复杂度在O(N2)O(N^2)O(N2),结果可想而知超时 #include<bits/stdc++.h>//超时的代码 using namespace std; int solve(int n, v...

C++ 动态规划

2022-04-10

19 689

题解 | #乘积为正数的最长连续子数组#

解题思路1：用0分割数组记录每一段的第一个负号和最后一个负号，以及负号的个数对于每一段，如果负号的个数为偶数则此整段就是长度如果负号的个数为奇数，则比较该段开始到第一个负号的长度a和最后一个负号到结尾的长度b。总长度-min（a，b）就是该段的长度比较每段长度取最大值即可。 #incl...

C++ 动态规划

2022-04-10

0 409