ButterFlyEffect

分类

题解(6)

/ 注册

全部文章（共2篇）

时间复杂度O(n)的非典型题解

本题第一时间想到的解法就是排序，但是这样不符合O(n)的时间复杂度要求。另外一种思路就是用一个set记录每个元素的位置，然后遍历数组的元素，对每个元素做向上向下的遍历，统计连续的长度。几个点：1 普通的set查找是O(logN)的，改成hash set就可以认为是O(1)的了。2 在之前序列统计过的...

贪心子集问题连续子区间问题

2020-11-08

0 708

动态规划

又是一个求连续区间数组的问题，典型的动态规划问题。和求最大区间和不同的是，如果我们依然尝试用dp[i]表示以a[i]结尾的子区间的最大成绩。会发现由于负数的存在，会导致乘法结果反转。dp[i-1]a[i]反倒变成了最小值，无法得到状态转移方程。沿着乘法的特性看，如果a[i]为负数，那么dpa[i]时...

动态规划连续子区间问题

2020-10-27

17 1021