最大子列问题与分治算法

本文主要是介绍最大子列问题与分治算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

        今天做到了一个最大子列的问题，题目如下：

7-4 最大子列和问题

给定K个整数组成的序列{ N1​, N2​, ..., NK​ }，“连续子列”被定义为{ Ni​, Ni+1​, ..., Nj​ }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2：个随机整数；
• 数据3：个随机整数；
• 数据4：个随机整数；
• 数据5：个随机整数；

输入格式:

输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6
-2 11 -4 13 -5 -2

结尾无空行

输出样例:

20

结尾无空行

        说来惭愧看到这个题的一瞬间我脑子里先出现的是暴力遍历一遍，但我知道这样肯定是不行的，绝对会超时。

        题目让我们求一段数里面和最大的子列在用实例自己演示的时候我发现可以不用每个数都作为某个字段的开头去遍历一遍，只要从左往右加，一直更新记录最大的字段和，如果此时的字段和为负数就直接把之前的字段都抛弃就行了，因为任何数加负数都不会更大。代码如下：

#include<iostream>
using namespace std;


int main()
{
    int n,a[100010]={0};
    int S=0,s=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++)
    {
        s+=a[i];//只管加就行
        if(s>S)S=s;//保持更新最大的子段和
        else if(s<0)//出现负数让s归0舍弃之前的字段
        s=0;
    }
    
    cout<<S;
}

        后来我在查阅网上的资料的时候得知我的代码其实是属于贪心算法，他的贪心代码是这么写的：

#include<vector>
#include<iostream>
using namespace std;
int theLargestSubParagraphSum(vector<int>&arr){
    int pre=0;
    int maxAns=arr[0];
    for(int i=0;i<arr.size();i++){
        pre=max(arr[i],arr[i]+pre);
        maxAns=max(maxAns,pre);
    }
    return maxAns;
}
int main()
{
    vector<int>p={-20,11,-4,13,-5,-2};
    cout<<theLargestSubParagraphSum(p);
	return 0;
}

(10条消息) 分治算法——最大子段和问题_秃头的毛睿的博客-CSDN博客_分治法求最大子段和问题

        顺着他的博客看我又得知这个问题可以运用分治的算法

        其实我对于分治算法的了解仅限于皮毛，分治正如其字面意思分而治之嘛，不过看上去是两个字其实分治算法是有三步的：

        1.分：把一个复杂的问题分成很多同样的简单的小问题

        2.治：解决这个简单的小问题

        3.归：递归！把这些小问题的解答归一成为这个复杂问题的解

        虽然理论层面的解释我是知道的但我实在是想不出来这个最大子段问题该如何分成相同的小问题

        然而这位博主是这么分而治之的：

我们分析以下这个问题，我们要知道一个数组的最大子序列和，这个子序列要么只落在这个数组中位的左侧，要么只落在中位的右侧，还有就是横跨中位的子序列，这样我们就可以写一个函数，专门用来求解一个数组的指定两个指针之间的最大子序列

#include<vector>
#include<iostream>
using namespace std;
int theLargestSubParagraphSum(vector<int>&num,int left,int right){
    int sum=0,midSum=0,leftSum=0,rightSum=0;
    int center;
    int s1,lefts,s2,rights;
    if(left==right){
        sum=num[left];
    }
    else{
        center=(left+right)/2;
        leftSum=theLargestSubParagraphSum(num,left,center);//如果子序列的和最大的子序列是在中心的左侧
        rightSum=theLargestSubParagraphSum(num,center+1,right);//如果子序列的和最大的子序列是在中心的右侧
 
        s1=0,lefts=0;
        for(int i=center;i>=left;i--){
            lefts+=num[i];
            if(lefts>s1)
                s1=lefts;
        }
        s2=0,rights=0;
        for(int i=center+1;i<=right;i++){
            rights+=num[i];
            if(rights>s2)
                s2=rights;
        }
        midSum=s2+s1;
        sum=max(max(leftSum,rightSum),midSum);
    }
    return sum;
}
int main()
{
    vector<int>p={-20,11,-4,13,-5,-2};
    cout<<theLargestSubParagraphSum(p,0,p.size()-1);
	return 0;
}

        真是不得不说递归是真的深奥，复杂问题简单话，把那么复杂的运算简化到两个整数比大小，tql，学到了。

这篇关于最大子列问题与分治算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！