leetcode5dp-Awesome:CS技能

leetcode5 dp Awesome 算法秒撕 ----排序---- 快速排序 * 参考算法导论 partition,将数组in-place地分成比pivot小的一边和比pivot大的一边； 多少有些分治的意思 随机产生pivot，并将其换到最后 partition结束后，将其换到i+1的位置 堆排序 * 参考算法导论 最大堆 A.val < A.parent.val 整个二叉树除了最底一层都是满的 i LEFT => 2i; RIGHT => 2i+1 保持堆的顺序正确 O(lgn) 由无序数组建堆 O(n) 堆排序 O(nlgn) => 抽取顶部元素后，用最末元素补上并调整树 冒泡排序 ----分治---- 第k大的数 * LeetCode 215 partition，而且单边就行，O(n) 数组连续的最大和 * 和一些炒股问题类似 数组中有正有负有0 解法1： 分治 => max{左边最大，右边最大，跨中间最大} 解法2（LeetCode & 剑指offer63）： 股票低点买入，高点售出 维护一个当前的最低值，和当前的最大利润；最后返回当前最大利润 int max_ = I