最大子数组问题（动态规划）--【算法导论】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最大子数组问题（动态规划）--【算法导论】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2397字，纯文字阅读大概需要4分钟。

内容图文

原文链接：http://www.cnblogs.com/riasky/p/3508609.html

前些天学车...真是相当累啊，比上课累，现在终于可以休息了...

重新看《算法导论》，不过这下可得认真看了，9个月不到就得去找工作了，与我同样的大三党们一样加油咯...

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

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，则其对后面子数组相加无帮助，此时重置dp为array[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 <iostream>

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<<"最大子序列的下标:"<<start<<"->"<<end<<endl;
    return MaxSumSub;

}

int main()
{
    int a[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    //int a[] = {23, 4};
    int length = sizeof(a) / sizeof(int);

    cout<<FindMaxSubarray(a, length);
    return 0;
}

 

最大子序列即为{18, 20, -7, 12};

上述dp即为动态记录寻找最大子数组的过程，大家也可以进行输出看一下；

 

欢迎大家指点，o(∩_∩)o

 

转载于:https://www.cnblogs.com/riasky/p/3508609.html

内容总结

以上是互联网集市为您收集整理的最大子数组问题（动态规划）--【算法导论】全部内容，希望文章能够帮你解决最大子数组问题（动态规划）--【算法导论】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---