精华内容
下载资源
问答
  • 最大连续子序列和(分治法实现) 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1]...

    求最大连续子序列和(分治法实现)

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
    示例:
    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

    tips:这里的时间复杂度为O(nlogn),本题的思路是二分查找法中学到的分治法,明确一点,连续子数组在数组中出现的位置有三种,一种是中间,一种是左半部分,一种是右半部分,而左半部分和右半部分的求得又是与原始数组的相同实现,于是将其分成一个个小块,最后逼近基线条件:只有一个元素.若其大于零,则为元素本身,小于零则为零.注意递归过程中返回的是左边,右边,中间的最大值.

    #include<stdio.h>
    int Maxsubsum(int a[],int Left,int Right)
    {
        int Center,i,Leftsum,Rightsum,Leftbordersum=0,Rightbordersum=0,Maxleftbordersum=0,Maxrightbordersum=0,max;
        //Center为中间的界线,Leftsum为递归过程中的左边最大,Rightsum为递归过程中的右边最大,Ma
        //xleftbordersum为中间靠左的最大,Maxrightbordersum为中间靠右的最大,max为三者最大
    
        if(Left==Right)
            {
                if(a[Left]>0)
                return a[Left];
        else return 0;
            }/*基线条件*/
    
        Center=(Left+Right)/2;
        Leftsum=Maxsubsum(a,Left,Center);//递归调用,分的过程
        Rightsum=Maxsubsum(a,Center+1,Right);//递归调用,分的过程
        for(i=Center;i>=Left;i--)
            {
                Leftbordersum+=a[i];
                if(Maxleftbordersum<Leftbordersum)
                    Maxleftbordersum=Leftbordersum;
            }                              //求出中间靠左最大
            
        for(i=Center+1;i<=Right;i++)
            {
                Rightbordersum+=a[i];
                if(Maxrightbordersum<Rightbordersum)
                    Maxrightbordersum=Rightbordersum;
            }                              //求出中间靠右最大
            max=Rightsum>Leftsum?Rightsum:Leftsum;
            max=max>(Maxleftbordersum+Maxrightbordersum)?max:Maxleftbordersum+Maxrightbordersum;//三者最大
            
            return max;//返回值
    }
    
    int main()
    {
        int b[9]={-2,1,-3,4,-1,2,1,-5,4};
        
        printf("%d",Maxsubsum(b,0,8));
        
        return 0;
    }
    
    
    展开全文
  • 给n个数,要求n个数的最大连续子序列和。 DP在O(n)的时间内就能求出,很简单。 但这里用分治的思想去做, 复杂度是O(nlogn), 二分用了O(logn),每次二分内的处理用了O(n) 将一个序列对半切(mid),那么这个最大...

    给n个数,要求n个数的最大连续子序列和。   DP在O(n)的时间内就能求出,很简单。

    但这里用分治的思想去做, 复杂度是O(nlogn),  二分用了O(logn),每次二分内的处理用了O(n)

     

    将一个序列对半切(mid),那么这个最大连续子序列和要么在[l,mid],要么在[mid+1,r],要么跨越两边。

    那么就要求出[l,mid]的最大连续子序列和, [mid+1,r]的连续子序列和,  跨越两边的连续子序列和

    前两个问题是子问题,可以递归去解决。 所以只要解决第三个问题,然后返回三者中的最大者

    第三个问题,我们可以从中间开始,分别向两边枚举。

    枚举的时间复杂度是O(n),递归的深度是logn, 所以复杂度是O(nlogn)

     1 int fenzhi(int L, int R)
     2 {
     3     if(L==R)
     4         return a[L];
     5     int mid = (L+R)>>1;
     6     int LSum = fenzhi(L,mid);
     7     int RSum = fenzhi(mid+1,R);
     8     int MidSum1 = 0 , MidSum2 = 0,tmp = 0;
     9     for(int i=mid;i>=L; --i)
    10     {
    11         tmp += a[i];
    12         if(tmp>MidSum1)
    13         {
    14             MidSum1 = tmp;
    15         }
    16     }
    17     tmp = 0;
    18     for(int i=mid+1;i<+R;++i)
    19     {
    20         tmp += a[i];
    21         if(tmp>MidSum2)
    22             MidSum2 = tmp;
    23     }
    24     return max(LSum,MidSum1+MidSum2,RSum);
    25 }

     

    转载于:https://www.cnblogs.com/justPassBy/p/4852514.html

    展开全文
  • 求非连续子序列的问题用DP很好解决,但是**分治法**就比较难了 假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13] 他的最大连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻 现在要求给L求S
  • JAVA实践分治法最大连续子序列求和

    千次阅读 2016-07-19 23:16:55
    前言最大连续子序列求和是指给定一串数字,算出一段连续的数字能求得的最大和。实现功能给定一串数字3, -4, 2, 5, 9, -3, 7, 9求连续的子序列的最大和3, -4, [2, 5, 9, -3, 7, 9]最大连续子序列的和是29实现参考概括...

    前言

    最大连续子序列求和是指给定一串数字,算出一段连续的数字能求得的最大和。

    实现功能

    给定一串数字

    3, -4, 2, 5, 9, -3, 7, 9

    求连续的子序列的最大和

    3, -4, [2, 5, 9, -3, 7, 9]

    最大连续子序列的和是29

    实现参考

    概括

     * 拆分序列(直到只剩下一个数的序列) ---->   左序列|右序列
     * 求左序列最大值
     * 求右序列最大值
     * 求跨边界的最大值
     * 求以上三个最大值的最大值
     * 不断重复

    中文版参考

     * 给定一个序列,求其中求和所得最大
     *
     * 假设存在一组序列
     * 3 -4 2 5 9 -3 7 9
     * 将这组数一分为2,得到
     * {2 -4 2 5 9}{-3 7 9}
     * 再对左边序列拆分
     * {2 -4}{2 5 9}
     * 再左拆分
     * {2}{-4}
     * 再左拆分
     * {2} 大于0,因此当前序列最大和为【2】(当前序列是指{2}这个只有一个数字的序列)
     * 处理右边
     * {-4} 小于0,返回0,可以看作是当前序列的最大和为【0】
     * 左右已处理完毕,回到上一层
     * 处理跨越边界的情况【跨越边界的详细描述请看下一个副标题】
     * {2}{-4}被拆成一个数字之前是存在边界的,现在求它们合起来的序列和
     * {2 -4}求最大和是【2】
     * 在【2】【0】【2】中取最大的,取得【【2】】
     * 现在对{2 5 9}进行一样的操作
     * 左拆分
     * {2}{5 9}
     * {2} 大于0,当前最大序列和为【2】
     * 处理右边的{5 9}
     * 左拆分
     * {5}{9}
     * {5}大于0,当前最大和为【5】
     * 处理右边
     * {9}大于0,当前最大和为【9】
     * 左右处理完毕,处理跨边界的情况
     * {5 9}求和是【14】
     * 处理完毕,在【5】【9】【14】中取最大值,【【14】】
     * 再回上一层
     * 对{2 5 9}求和【16】
     * 再取【2】【14】【16】三者的最大【【【16】】】
     *
     * 接下来所有的操作都同上

    跨边界求和详细描述

     * 假定存在以下序列
     * {4 -3 5 -2}
     * 
     * 左拆分
     * {4 -3}{5 -2}
     * 左拆分
     * {4}{-3}
     * 左拆分
     * {4}  求得当前序列最大和为【4】
     * 处理右边的{-3}
     * {-3}小于0,所以返回0,则最大和为【0】
     * 它们被拆分之前是{4 -3},所以{4 -3}的最大和是【4】《此处是求跨越边界的和,但是两个数不容易理解,放到下面再说》
     * 处理右边的
     * {5 -2}
     * 左拆分
     * {5}{-2}
     * 左拆分
     * {5}  求得序列最大和为【5】
     * 处理右边的{-2}
     * {-2}小于0,所以返回0,最大和为【0】
     * 它们被拆分前是{5 -2},所以{5 -2}最大和是【5】《此处是求跨越边界的和,但是两个数不容易理解,放到下面再说》
     * {4 -3}{5 -2}处理完毕,最大和分别是【4】【5】
     * ------------------------------------------------------------
     * 它们被拆分之前是{4 -3 | 5 -2}《开始说关键的跨越边界求和》
     * 先说结果:
     *      左边的最大和(4 + (-3)) = 1
     *      右边的最大和5
     *      左右相加得【6】
     *
     * 为什么是左边4+(-3)呢?
     * 首先以|为边界向左扫描求最大和
     * 因为是从【中间向左】扫,第一个扫到的数是-3
     * 再向左扫,是44比-3大吧!
     * 要包含4,就必须把-3加上
     * 因为要跨越边界,-3肯定要经过的,才能形成连续的序列。
     * 左边扫描完了,就从【中间向右】扫
     * 第一个发现5,扫向下一个,发现是-2,相加起来还不如一个5呢
     * 于是就不要-2了。为什么可以不要?因为这是一个从左往右的序列~
     * 而-2在最右边,当然是可以抛弃的了。
     *
     * 如果-2 后面还有一个数,比如3的话,是{5 -2 3},这时把三个数加起来是6,比5大,就需要把三个数都包含起来。
     * 因为三个数加起来比5大恩。就是这个理。
     *
     * 此时可以知道{4 -3 | 5 -2},最大和是左边的1加上右边的5得到【6】。

    再看概括

     * 拆分序列(直到只剩下一个数的序列) ---->   左序列|右序列
     * 求左序列最大值
     * 求右序列最大值
     * 求跨边界的最大值
     * 求以上三个最大值的最大值
     * 不断重复

    代码实现

    public class MaxSubSequent {
        static int[] arr = new int[] {3, -4, 2, 5, 9, -3, 7, 9};
        public static void main(String[] args) {
            System.out.println(maxSubSequent(0, arr.length - 1));
        }
        public static int maxSubSequent(int startIndex, int endIndex) {
            if (startIndex ==  endIndex) {
                return arr[startIndex] > 0 ? arr[endIndex] : 0;
            }
            int center = (startIndex + endIndex) / 2;
            //一直向左拆分,直到海枯石烂,然后得到左子序列的最大值
            int maxLeftValue = maxSubSequent(startIndex, center);
            //一直向右拆分,直到海枯石烂,然后得到右子序列的最大值
            int maxRightValue = maxSubSequent(center + 1, endIndex);
    
            //临时变量,存储序列相加的值
            int tValue;
    
            //从中间向左扫描求最大序列和
            int centerToLeftMaxValue = 0;
            tValue = 0;
            for (int i = center; i >= startIndex; i--) {
                tValue += arr[i];
                //如果没有大于0的数,那么,就当左边的是0了
                if (tValue > centerToLeftMaxValue) {
                    centerToLeftMaxValue = tValue;
                }
            }
    
            //从中间向右扫面最大序列和
            int centerToRightMaxValue = 0;
            tValue = 0;
            for (int i = center + 1; i <= endIndex; i++) {
                tValue += arr[i];
                if (tValue >= centerToRightMaxValue) {
                    centerToRightMaxValue = tValue;
                }
            }
    
            /**
             *  经过上面的操作,已经知道了三个值
             *  maxLeftValue左序列的最大和
             *  maxRightValue右序列的最大和
             *  左右合并的之后序列的最大和
             *  再在这三个最大和之间取最大值即可
             */
            return Math.max(Math.max(maxLeftValue, maxRightValue), centerToLeftMaxValue + centerToRightMaxValue);
        }
    }

    结果

    29

    一点收获

    一开始看到分而治之一脸懵逼
    再看代码,离散懵逼
    实在没办法,就用文字写出了分治过程,然后发现,不懵逼了。
    碰到暂时看不懂的,好好摸清运行过程,写出了之后就可以发现哪里不严谨,并且会知道哪里需要是概念模糊,自己无法使用语言描述的,再看回去即可。

    END

    展开全文
  • =1)个整数的序列,求出其中最大连续子序列的和。例如序列(-2,,11,-4,13,-5,-2)的最大子序列和为20。规定一个序列的最大连续子序列和至少是0,如果小于0,其结果为0。 分治法 当n>1,取中间位置mid,将原...

    问题描述

    给定一个有n(n>=1)个整数的序列,求出其中最大连续子序列的和。例如序列(-2,,11,-4,13,-5,-2)的最大子序列和为20。规定一个序列的最大连续子序列和至少是0,如果小于0,其结果为0。

    分治法

    当n>1,取中间位置mid,将原序列一分为二->分别求出3中最大子序列和:完全在左序列,完全在右子序列,横跨两个序列(两个序列边界最大子序列和相加)->找出这3个子序列和中的最大值。

    #include<bits/stdc++.h>
    using namespace std;
    //三个数最大值
    long Max3(long a, long b, long c)
    {
    	return max(max(a,b),c);
    }
    //求序列a[s...t]中最大连续子序列
    long MaxSum(int a[], int s, int t)
    {
     	long maxlsum, maxrsum, maxl=0, maxr=0;
     	if(s==t) //序列只有1个元素
      		return max(a[s], 0);
    	 int mid=(s+t)/2;
    	 maxlsum=MaxSum(a, s, mid); //左最大子序列和 
    	 maxrsum=MaxSum(a, mid+1, t);  //右最大子序列和
    	 long templsum=0;
    	 for(int i=mid; i>=s; i--) //求左边加上mid元素构成的序列和
    	 {
    		  templsum+=a[i];
    		  if(templsum>maxl) maxl=templsum;
    	 } 
    	 long temprsum=0;
    	 for(int i=mid+1; i<=t; i++) //求右边构成的序列和
    	 {
    		  temprsum+=a[i];
    		  if(temprsum>maxr) maxr=temprsum;
    	 } 
    	 return Max3(maxlsum, maxrsum, maxl+maxr);
    } 
    int main()
    {
    	 int a[]={-2,11,-4,13,-5,-2};
    	 int n=sizeof(a)/sizeof(*a);
    	 cout<<"最大连续子序列和为"<<MaxSum(a, 0, n-1);
    }

    时间复杂度:O(nlog(2)(n))

    动态规划

    状态转移方程:边界条件dp[0]=0;dp[j]=MAX{dp[j-1]+aj,aj}即当dp元素≤0时放弃前面选取的元素,从aj开始重新选取。
    若要求出序列,在dp中从该位置往前找,找到第一个≤0的元素dp[k],则a序列中k+1开始到maxj位置的所有元素恰好构成最大连续子序列。

    # include<bits/stdc++.h>
    using namespace std;
    #define MAX 50
    int dp[MAX];
    int maxS=0, maxi=0;
    
    void MaxSum(int a[], int start, int end)
    {
    	dp[0]=0;
    	for(int i=start; i<=end; i++)
    	{
    		dp[i]=max(dp[i-1]+a[i], a[i]);
    		if(dp[i]>maxS)
    		{
    			maxS=dp[i];
    			maxi=i;
    		}
    	}	
    }
    
    void PrintA(int a[], int k)
    {
    	int t;
    	for(int i=k; i>=0; i--)
    	{
    		if(dp[i]<=0)
    		{
    			t=i;
    			break;
    		}
    	} 
    	for(int i=t+1; i<=k; i++)
    		cout<<a[i]<<" ";
    	cout<<endl;
    }
    
    int main()
    {
    	int a[]={-2,11,-4,13,-5,-2};
    	int n=sizeof(a)/sizeof(*a);
    	MaxSum(a, 0, n-1);
    	cout<<"最大连续子序列和为"<<maxS<<endl;
    	cout<<"该子序列是:"; 
    	PrintA(a, maxi);
    	return 0; 
    }

    时间复杂度O(n)

    展开全文
  • 俺是菜鸟了解一下,这是我在算法学习中的一些想法,如果有写的不好的还请谅解,欢迎学习交流_(:3」∠)_ 问题:有长度为n的整数序列,求一段连续子序列,要求该子序列的和为最大,并求出最大值。 用分治法解决最...
  • 最大连续子序列分治法) 原理:  一串数组可以对半分,一串数组的最大连续子序列可能是在左端,右端以及跨越中间  依次递归分解求得最小块的最大值,再向上组合成整段最大连续子序列 #include #include ...
  • 分治法之求最大连续子序列

    千次阅读 2017-03-05 11:52:57
    1.最大子序列在数组中点的左边 2.最大子序列在数组中点的右边 3.最大子序列跨越数组中点#include using namespace std; int FIND_MAX_CROSSING_SUBARRAY(int a[],int low,int high) { int mid = (low+high)/2; ...
  • 求解最大连续子序列和问题 【问题描述】 给定一个有n(n>=1)个整数的序列,要求求出其中最大连续子序列的和 【样例输入】 6 -2 11 -4 13 -5 -2 【样例输出】 20 【问题求解】 对于含有N个整数的序列a[0…n-1],...
  • 使用分治法最大连续子序列的和 设有一个整数数列a[n],1≤s, t≤n。求a[n]的一个子数列a[s, t],使得该子数列的和尽可能大。 若这个和小于0,则输出0。 【算法本体】 (参考代码中,因为要与暴力法对比运行时间,...
  • #include int FindMaxCrossSum(int A[],int left,int right); int FindMaxSubSeq(int A[],int left,int right); int main() { int A[]={1,-5,9,8,1,-2}; int max=FindMaxSubSeq( A,0,5);...printf("%d",max);...
  • 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你...
  • 看书、思考、写代码。 /*************************************** ... * 题目:分治法求数组最大连续子序列和 * 思路:分解成子问题+合并答案 * 时间复杂度:O(n lgn) * 空间复杂度:O(1) ****...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 200
精华内容 80
关键字:

最大连续子序列分治法