乘积最大子序列

题目描述:

找出一个序列中乘积最大的连续子序列(包含至少一个元素)

算法思路:

可以将问题划分为:对于序列nums[n],算出包含nums[i], 1 < i < n的乘积最大子序列的乘积max[i],然后从中找出最大的乘积;

阅读全文

数组中的第K大元素

题目描述:

找出一个数组中的第K大元素

算法思路:

对于nums[low, … high] 首先找一个基准值(在这里,选择划分范围内的最后一个元素nums[high]作为基准),交换元素,使得基准值之前的元素都大于它,之后的元素都小于它(在代码实现中的方法是:用index维护比基准值大的元素放的位置,实际上就是从范围内的第一个元素开始往后放,扫描nums[low]到nums[high]的元素,如果比基准值大,就将它和nums[++index] 交换,最后将nums[++index]和num[high]交换),然后比较基准值的位置index和k-1的大小,如果相等就直接返回表示找到了,如果小于,意味着第K大元素在基准值的后面,那么在index+1,high中找,如果大于,在low, index-1中找;

阅读全文