外包网站建设,英文网站的建设意义,紫川网站建设,wordpress 动态js求最大子段和
此类问题通常是求数列中连续子段和的最大值#xff0c;经典的股票问题就是考察的这个思想及拓展。 例题#xff1a; AcWing:1054. 股票买卖 Leetcode:53. 最大子数组和
分治法O(nlogn)
此类问题时分适合采用分治思想#xff0c;因为所有子区间 [ s t a r t …求最大子段和
此类问题通常是求数列中连续子段和的最大值经典的股票问题就是考察的这个思想及拓展。 例题 AcWing:1054. 股票买卖 Leetcode:53. 最大子数组和
分治法O(nlogn)
此类问题时分适合采用分治思想因为所有子区间 [ s t a r t , e n d ] [start, end] [start,end]只可能有以下三种可能
在 [ 1 , n 2 ] [1,\frac{n}{2}] [1,2n]这个区域内。在 [ n 2 1 , n ] [\frac{n}{2}1, n] [2n1,n]这个区域内。左边界位于 [ 1 , n 2 ] [1,\frac{n}{2}] [1,2n]右边界位于 [ n 2 1 , n ] [\frac{n}{2}1 ,n] [2n1,n]内。
这三种情况的最大值即为所求。前两种情况符合子问题递归特性可以通过递归求出。
在第三种情况中 n 2 , n 2 1 \frac{n}{2},\frac{n}{2}1 2n,2n1必然包含在内因此可以利用第二种穷举的思路分别向左右扩张求出。
int maxx -INF;
int maxInterval(vectorint a, int l, int r) {if(l r) {return (a[l] maxx) ? a[l] : maxx;}int sum_l 0, sum_r 0;int mid (l r) 1;sum_l maxInterval(a, l, mid);sum_r maxInterval(a, mid 1, r);int s1 0, x 0;for(int i mid; i 0; i -- ) {x a[i];if(x s1) s1 x;}int s2 0, y 0;for(int i mid 1; i r; i ) {y a[i];if(y s2) s2 y;}maxx max(sum_l, s1 s2);maxx max(maxx, sum_r);return maxx;
}动态规划思路O(n)
如果我们用常规思路来枚举所有数字并判断当前数字是否应该加入到最大子段那么会发现当前数字的选择与否并不是由前面已经遍历过的数字所决定而是由其后面的数字来决定这也就导致了问题的有后效性。
当出现有后效性问题时我们当前对子问题做出的选择就不一定为最优解因为会受到后续数据的影响。
后效性问题是动态规划中一个非常重要的概念在此引用《算法竞赛进阶指南》李煜东著中的一段话 为了保证计算子问题能够按照顺序、不重复地进行动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做无后效性。换言之动态规划对状态空间的遍历构成一张有向无环图遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的状态图中的边则对应状态之间的转移转移的选取就是动态规划中的决策。 在此问题中我们需要换一种思路来避免有后效性问题我们可以将遍历到的数字看作必选项然后判断是否要加上前面的和。我们考虑使用dp[i]来表示以a[i]来结尾的子数组的最大子段和那么我们可以得到状态转移方程为 d p [ i ] m a x ( a [ i ] , d p [ i − 1 ] a [ i ] ) dp[i] max(a[i], dp[i - 1] a[i]) dp[i]max(a[i],dp[i−1]a[i]) 那么结果即为 r e s m a x ( r e s , d p [ i ] ) resmax(res, dp[i]) resmax(res,dp[i]).
int MaxInterval(vectorint a, int len) {vectorint dp(len);int res -INF;dp[0] a[0];for(int i 1; i len; i ) {dp[i] max(a[i], dp[i - 1] a[i]);res max(res, dp[i]);}return res;
}扫描法O(n)
动态规划思路的一个空间优化版本。
由于只和当前元素前面的最大值有关因此只需要记录前面最大值即可。
前面的最大值表示前 i − 1 i-1 i−1个问题的最优解。
int maxInterval(vectorint v, int len) {int res v[0], mi min(0, v[0]), sum v[0];for(int i 1; i len; i ) {sum v[i];res max(res, sum - mi);mi min(mi, sum);}return res;
}
