2019年08月19日(星期一)  农历:己亥年七月十九
  • 首页
  • JAVA
  • Java最大子数组问题算法导论

作者:三年。分类: JAVA

《算法导论》中引入这个问题是通过股票的购买与出售,将前一天的当天的股票差价重新表示出来,即转为了一个最大子数组的问题 ,具体内容我不多说,转的内容是:

13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7

找到这连续的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,则其对后面子数组相加无帮助,此时重置dparray[i], 并且记录的起始位置重新标记;

if(dp[i - 1] <= 0) //前面的<0,直接丢弃

{

dp[i] = array[i];

temp = i; //记录起始为止

}

否则,继续往后延伸;

dp[i] = array[i] + dp[i - 1]; //往后求和

最后判断最大子数组值就行,同时标记起始与结束位置

if(dp[i] > MaxSumSub) //找到到i为止的最大子数组

{

MaxSumSub = dp[i]; //最大...

start = temp; //标记起始

end = i; //标记此时的结束位置

}

代码:

#include

using namespace std;

int FindMaxSubarray(int array[], int length)

{

int start = 0, end = 0; //记录最大子数组的起始位置(在数组中的下标)

int MaxSumSub; //最大子数组的值

int* dp = new int[length]; //动态规划记录

dp[0] = array[0]; //初始为第一个数

MaxSumSub = dp[0]; //最大值初始为第一个数

int temp = 0; //

for(int i = 1; i < length; i++)

{

if(dp[i - 1] <= 0) //前面的<0,直接丢弃

{

dp[i] = array[i];

temp = i; //记录起始为止

}

else

dp[i] = array[i] + dp[i - 1]; //往后求和

if(dp[i] > MaxSumSub) //找到到i为止的最大子数组

{

MaxSumSub = dp[i]; //最大...

start = temp; //标记起始

end = i; //标记此时的结束位置

}

}

cout<<"最大子序列的下标:"<"<

 

最大子序列即为{18, 20, -7, 12}; 上述dp即为动态记录寻找最大子数组的过程,大家也可以进行输出看一下; 欢迎大家指点,o(∩_∩)o

温馨提示如有转载或引用以上内容之必要,敬请将本文链接作为出处标注,谢谢合作!

已有 0/1454 人参与

发表评论:



手Q扫描加入Java初学者群