精华内容
下载资源
问答
  • = 1)个整数的序列,求出其中最大连续子序列的和。例如序列(34,-20,30,-50,60,-20,30,41,-30,-10)最大子序列和为111,序列(-2,11,-4,13,-5,-2)最大子序列和为20。规定一个序列的最大连续子序列和至少为0。 二、...

    一、问题描述

    给定一个有n(n >= 1)个整数的序列,求出其中最大连续子序列的和。例如序列(34,-20,30,-50,60,-20,30,41,-30,-10)最大子序列和为111,序列(-2,11,-4,13,-5,-2)最大子序列和为20。规定一个序列的最大连续子序列和至少为0。

    二、问题求解

    1、对于含有n个整数的序列,若n=1,表示序列仅有一个元素,该元素大于0,则返回该元素,否则返回0。

    if(left == right){
    	if(a[left]>=0)
    		return a[left];
    	else
    		return 0;
    }
    

    2、如果n>1,则采用分治法求解最大连续子序列和。取中间位置 mid = ( left + right ) /2 。则最大连续子序列和只可能出现在3个地方。

    • ①该子序列全部落在左半部分,即a[0,···mid]中,该问题和原本问题解决方法一样,采用递归求出其最大连续子序列和maxLeftSum
    • ②该子序列全部落在右半部分,即a[mid+1,···n-1]中,该问题和原本问题解决方法一样,采用递归求出其最大连续子序列和maxRightSum
    • ③该子序列跨越序列a的中部而占据左右两部分。也就是说,这种情况下的最大连续子序列和必然包括mid元素,则先求出maxLeftBorderSum从mid(终点)到left的最大连续子序列和找到左边最大连续子序列和的起点位置,将左边到mid的最大连续子序列和赋值给maxLeftBorderSum。再求出maxRightBorderSum从mid(起点)到right的最大连续子序列和,找到右边最大连续子序列和的终点位置,将mid到右边的最大连续子序列和赋值给maxRightBorderSum。这种情况下的最大连续子序列和为 maxMidSum =maxLeftBorderSum+maxRightBorderSum
      3、整个序列a的最大连续子序列和为maxMidSum 、maxLeftBorderSum、maxRightBorderSum。将三者进行大小比较即为最终结果。

    三、完整代码展示(C语言)

    //求解最大连续子序列和问题 
    #include<stdio.h>
    int num[10] = {34,-20,30,-50,60,-20,30,41,-30,-10}; 
    //int num[6] = {-2,11,-4,13,-5,-2}; 
    int max3(int a,int b,int c){ //求三者的最大值
    	if(a < b)
    	a = b;
    	if(a < c)
    	a = c;
    	return a;	
    }
    int maxSubSum(int a[],int left,int right){
    	int i,j;
    	int maxLeftSum,maxRightSum;
    	int maxLeftBorderSum,leftBorderSum;
    	int maxRightBorderSum,rightBorderSum;
    	if(left == right){  //只有一个元素的情况
    		if(a[left]>=0) 
    			return a[left];
    		else
    			return 0;
    	}
    	int mid = (left+right)/2; //取中间位置
    	
    	maxLeftSum = maxSubSum(a,left,mid); //求左边的最大序列和
    	maxRightSum = maxSubSum(a,mid+1,right); //求右边的最大序列和
    	
    	maxLeftBorderSum = 0;
    	leftBorderSum = 0;
    	maxRightBorderSum = 0;
    	rightBorderSum = 0;
    //最大连续子序列在序列a的中部而占据左右两部分情况
    	for(i=mid;i>=left;i--){ //求mid到左边的maxLeftBorderSum
    		leftBorderSum += a[i];
    		if(maxLeftBorderSum < leftBorderSum)
    			maxLeftBorderSum = leftBorderSum;
    	}
    	
    	for(j=mid+1;j <= right;j++){ //求mid到右边的maxRightBorderSum
    		rightBorderSum += a[j];
    		if(maxRightBorderSum < rightBorderSum)
    			maxRightBorderSum = rightBorderSum;
    	}
    	return max3(maxRightBorderSum,maxLeftBorderSum,maxLeftBorderSum+maxRightBorderSum);		
    }
    
    int main(){
    	printf("maxSubSum= %d\n",maxSubSum(num,0,9));
    	return 0;
    }
    
    展开全文
  • 最大连续子序列和(分治法实现) 给定一个整数数组 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;
    }
    
    
    展开全文
  • 俺是菜鸟了解一下,这是我在算法学习中的一些想法,如果有写的不好的还请谅解,欢迎学习交流_(:3」∠)_ 问题:有长度为n的整数序列,求一段连续子序列,要求该子序列的和为最大,并求出最大值。 用分治法解决最...

        俺是菜鸟了解一下,这是我在算法学习中的一些想法,如果有写的不好的还请谅解,欢迎学习交流_(:3」∠)_

        问题:有长度为n的整数序列,求一段连续的子序列,要求该子序列的和为最大,并求出最大值。

        用分治法解决最大子序列和问题使用的是递归,它的思想是:

    1.将一个长度为n的序列,一分为二变为两个长度为n/2的子序列,继续将子序列们一分为二,直到每个子序列只含有1个整数。

    2.此时问题已经足够小,“最大子序列和”有以下三种情况:左边序列的最大子序列和、右边序列的最大子序列和和处在中间位置上的最大子序列和,我们通过比较,得到三者中的最大值。

    3.再将这些“小问题”合并,使用同样的比较方法逐步向上合并这些“左右序列”,直到得到整个序列的最大子序列和,解决问题。


        在这个问题中,分为两种情况:1.序列含有正整数;2.序列不含正整数。我的想法是可以对这两种情况分别使用对应的函数。

        第一种情况,序列含有正整数,算法的时间复杂度为O(nlog(n)):

    int MaxSubseqSum(int a[],int left,int right)
    {
    	int maxLeftSum,maxRightSum,maxMidSum;
    	int maxLeftBorderSum,LeftBorderSum;
    	int maxRightBorderSum,RightBorderSum;
    	int mid;
    	int i;
    	if(left==right)	//递归出口,子序列只有一个元素时
    		return a[left];
    	mid=(left+right)/2;	//求中间位置
    	maxLeftSum=MaxSubseqSum(a,left,mid);	//求左边序列的最大子序列和
    	maxRightSum=MaxSubseqSum(a,mid+1,right);	//求右边序列的最大子序列和
    	maxLeftBorderSum=0;
    	LeftBorderSum=0;
    	for(i=mid;i>=left;i--)	//从中间位置向左找靠边界的最大子序列
    	{
    		LeftBorderSum+=a[i];
    		if(LeftBorderSum>maxLeftBorderSum)
    			maxLeftBorderSum=LeftBorderSum;
    	}
    	maxRightBorderSum=0;
    	RightBorderSum=0;
    	for(i=mid+1;i<=right;i++)	//从中间位置向右找靠边界的最大子序列
    	{
    		RightBorderSum+=a[i];
    		if(RightBorderSum>maxRightBorderSum)
    			maxRightBorderSum=RightBorderSum;
    	}
    	maxMidSum=maxLeftBorderSum+maxRightBorderSum;	//得到处在中间位置上的最大子序列和
    	return max3(maxLeftSum,maxRightSum,maxMidSum);
    }

      第二种情况,序列不含正整数,可以改为使用分治法取序列中最大的数,算法的时间复杂度为O(log(n))

    int MaxNum(int a[],int left,int right)
    {
    	int maxLeft,maxRight;
    	int mid;
    	if(left==right)
    		return a[left];
    	mid=(left+right)/2;
    	maxLeft=MaxNum(a,left,mid);
    	maxRight=MaxNum(a,mid+1,right);
    	return maxLeft>maxRight?maxLeft:maxRight;
    }

    完整运行代码:

    #include<stdio.h>
    #define MAXSIZE 100
    
    int max3(int a,int b,int c)
    {
    	if(a>b) return a>c?a:c;
    	else return b>c?b:c;
    }
    
    int MaxSubseqSum(int a[],int left,int right)
    {
    	int maxLeftSum,maxRightSum,maxMidSum;
    	int maxLeftBorderSum,LeftBorderSum;
    	int maxRightBorderSum,RightBorderSum;
    	int mid;
    	int i;
    	if(left==right)	//递归出口,子序列只有一个元素时
    		return a[left];
    	mid=(left+right)/2;	//求中间位置
    	maxLeftSum=MaxSubseqSum(a,left,mid);	//求左边序列的最大子序列和
    	maxRightSum=MaxSubseqSum(a,mid+1,right);	//求右边序列的最大子序列和
    	maxLeftBorderSum=0;
    	LeftBorderSum=0;
    	for(i=mid;i>=left;i--)	//从中间位置向左找靠边界的最大子序列
    	{
    		LeftBorderSum+=a[i];
    		if(LeftBorderSum>maxLeftBorderSum)
    			maxLeftBorderSum=LeftBorderSum;
    	}
    	maxRightBorderSum=0;
    	RightBorderSum=0;
    	for(i=mid+1;i<=right;i++)	//从中间位置向右找靠边界的最大子序列
    	{
    		RightBorderSum+=a[i];
    		if(RightBorderSum>maxRightBorderSum)
    			maxRightBorderSum=RightBorderSum;
    	}
    	maxMidSum=maxLeftBorderSum+maxRightBorderSum;	//得到处在中间位置上的最大子序列和
    	return max3(maxLeftSum,maxRightSum,maxMidSum);
    }
    
    int MaxNum(int a[],int left,int right)
    {
    	int maxLeft,maxRight;
    	int mid;
    	if(left==right)
    		return a[left];
    	mid=(left+right)/2;
    	maxLeft=MaxNum(a,left,mid);
    	maxRight=MaxNum(a,mid+1,right);
    	return maxLeft>maxRight?maxLeft:maxRight;
    }
    
    void main()
    {
    	int a[MAXSIZE];
    	int count=0;
    	int i,n;
    	printf("序列长度:");
    	scanf("%d",&n);
    	printf("输入整数序列:");
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(a[i]<=0)
    			count++;
    	}
    	if(count==n)	//判断是否含有正整数
    		printf("最大子序列和:%d\n",MaxNum(a,0,n-1));
    	else
    		printf("最大子序列和:%d\n",MaxSubseqSum(a,0,n-1));
    
    }
    





    展开全文
  • =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)

    展开全文
  • JAVA实践分治法最大连续子序列求和

    千次阅读 2016-07-19 23:16:55
    前言最大连续子序列求和是指给定一串数字,算出一段连续的数字能求得的最大和。实现功能给定一串数字3, -4, 2, 5, 9, -3, 7, 9求连续的子序列的最大和3, -4, [2, 5, 9, -3, 7, 9]最大连续子序列的和是29实现参考概括...
  • 求解最大连续子序列和问题 【问题描述】 给定一个有n(n>=1)个整数的序列,要求求出其中最大连续子序列的和 【样例输入】 6 -2 11 -4 13 -5 -2 【样例输出】 20 【问题求解】 对于含有N个整数的序列a[0…n-1],...
  • 分治法之求最大连续子序列

    千次阅读 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; ...
  • 分治法之图解最大子序列

    千次阅读 2020-03-01 15:19:50
    给定一个长度为n的整数序列,求它的最大连续子序列和 -2,1,-3,4,-1,2,1,-5,4 最大连续子序列和为4+(-1)+2+1=6 注意题目说最大没有说最长 */ package 分治法; public class 最大连续子序列 { /**解法一:暴力...
  • 使用分治法最大连续子序列的和 设有一个整数数列a[n],1≤s, t≤n。求a[n]的一个子数列a[s, t],使得该子数列的和尽可能大。 若这个和小于0,则输出0。 【算法本体】 (参考代码中,因为要与暴力法对比运行时间,...
  • 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你...
  • 分治法求数组最大连续子序列的和

    千次阅读 2014-08-23 19:26:02
    #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);...
  • 给n个数,要求n个数的最大连续子序列和。 DP在O(n)的时间内就能求出,很简单。 但这里用分治的思想去做, 复杂度是O(nlogn), 二分用了O(logn),每次二分内的处理用了O(n) 将一个序列对半切(mid),那么这个最大...
  • 最大连续子序列和问题: 给定k个整数的序列{N1,N2,…,Nk },其任意连续子序列可表示为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= k。最大连续子序列是所有连续子序中元素和最大的一个。 这个问题的求解...
  • 最大连续子序列分治法) 原理:  一串数组可以对半分,一串数组的最大连续子序列可能是在左端,右端以及跨越中间  依次递归分解求得最小块的最大值,再向上组合成整段最大连续子序列 #include #include ...
  • 第一种方法:双指针枚举 public static int findLengthOfLCIS1(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int n = nums.length; int maxLength ...
  • //三者取最大 } int maxSubSum3(const vector<int>& a) { return maxSumRec(a,0,a.size()-1); } int main() { int n; cin>>n; vector<int> v; for(int i=0;i;i++) {int x;cin>>x,v.push_back(x);} cout(v);...
  • 写在前面,有个疑问,这种算法好像数组长度只能是偶数,但实际是奇数也可以,没想明白,改天在考虑。...先将数组一分为二,求出左半部分的最大子序列和,求出右半部分的最大子序列和,最后求出横跨中间的最大子序列和,
  • C++的作业,最大字段和问题 分治法,程序直接用dev就能运行。求一个序列的最大子段和即最大连续子序列之和。例如序列[4, -3, 5, -2, -1, 2, 6, -2]
  • 文章预览问题:求解最大连续子序列和问题思路一:穷举思路二:穷举思路三:穷举 问题:求解最大连续子序列和问题 题目: 给定一个有n(n>=1)个整数的序列,求解其中最大连续子序列的和。规定一个序列的...
  • 分治法最大子序列和------使用C语言一、问题提出二、算法分析三、程序设计四、程序结果显示 一、问题提出 给定一个序列,其中可能有正数也可能有负数,找出其中连续的一个子数列(不允许空序列),使它们的和尽...
  • 分治法最大连续和题目给出一个长为n的序列,求最大连续和解析对整个序列进行对半拆分,发现其就只有两种情况,第一种是最大序列完全在左半边或者右半边,第二种情况是左右半边都有,由此我们可以写出代码。...
  • ①蛮力(即暴力算法)实现: 代码实现: int maxSubSum1(int a[],int n){ int i,j,k; int maxSum=0,thisSum; for(i=0;i<n;i++){ for(j=i;j<n;j++){ thisSum=0; for(k=i;k<=j;k++) thisSum...
  • 求 在这个序列的所有子序列连续)中,最大的和是多少? 注意: 以下代码都要求最大和 【可为负数】,若要求最大和 【非负】,只需最后判断一下即可 1 算法1 #include<cstdio> using namespace std; // ...
  • 分治法最大子段和,适合刚接触数据结构的初学者
  • 最大连续子序列 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 45465 Accepted Submission(s): 20797 Problem Description 给定K个整数的序列{ N1, N2, ...
  • 求解最大连续子序列和问题 【问题描述】给定一个有n(n>=1)个整数的序列,求出其中最大连续子序列的和。例如序列(-2,,11,-4,13,-5,-2)的最大子序列和为20,序列(-6,2,4,-7,5,3,2,-1,6,-9,10,-2)的...
  • 最大连续子序列

    2018-04-16 16:32:27
    什么是最大连续子序列和问题?问题描述:给定一个序列(整数或浮点数),求出其中连续的子序列和最大的那一个。例:序列{-10 1 2 3 4 -5 -23 3 7 -21},其最大的连续子序列为{1 2 3 4}或{3 7},最大和为10.方法一:...
  • * 分治法求子序列最大和,体现递归的优点,时间复杂度O(N*logN) */ private static int maxSumRec(int[] a, int left, int right) { // TODO Auto-generated method stub if(left==right){ return a...
  • 其中dp[i]表示以nums[i]结尾的最大连续和。 这个公式就理解成: 对于当前这个数字,要么前面的对你有益,你加上; 要么前面对你无益,你不需要前面的。 所以,最后再额外使用一个空间,用来保留目前为止认为的最大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,907
精华内容 2,362
关键字:

最大连续子序列分治法