实质就是递归思想是分治
以上把代码就是把数组分成两部分,然后这两部分中再往下分直至if(low==high)
你对这个回答的评价是?
前些天学车...真是相当累啊比上課累,现在终于可以休息了...
重新看《算法导论》不过这下可得认真看了,9个月不到就得去找工作了与我同样的大三党们一样加油咯...
《算法导论》中引入这个问题是通过股票的购买与出售,将前一天的当天的股票差价重新表示出来即转为了一个最大子数组的子数组和最夶问题,具体内容我不多说转的内容是:
找到这连续的16个数里面的连续和最大的子数组;
书中练习部分说用设计非递归的,线性时间的算法我就YY为动态规划处理了;
从数组的子数组和最大左边界开始,从左至右处理记录到目前为止已经处理过的最大子数组。若已知A[1..j]的最夶子数组基于如下性质将解扩展为A[1...j+1]的最大子数组:A[1...j+1]的最大子数组要么是A[1...j]的最大子数组,要么是某个子数组A[i...j+1](1<=i<=j+1)在已知A[1...j]的最大子数组的孓数组和最大情况下,可以在线性时间内找出形如A[i...j+1]的最大子数组;
思想上述都将出来了只要将关键点写出即可:
如果前面若干和<0,则其對后面子数组相加无帮助此时重置dp为array[i],并且记录的起始位置重新标记;
最后判断最大子数组值就行同时标记起始与结束位置:
上述dp即為动态记录寻找最大子数组的子数组和最大过程,大家也可以进行输出看一下;
欢迎大家指点o(∩_∩)o
可使用分治法求解的一些经典问题(1)二分搜索(2)大整数乘法(3)Strassen矩阵乘法(4)棋盘覆盖(5)合并排序(6)快速排序(7)线性时间选择