精华内容
下载资源
问答
  • 最大子段和
    2021-11-07 20:14:47

    朴素问题

    先来一道朴素最大子段和
    https://www.luogu.com.cn/problem/P1115
    很简单就是给你一个序列,在这里面找到连续且非空的一段,让这一段和最大

    • d p [ i ] dp[i] dp[i]表示包含第 i i i个数的最大子段和,考虑如何转移,很简单,因为如果 d p [ i − 1 ] < 0 dp[i-1]<0 dp[i1]<0,那么如果第 i i i个数归类到前面,总不如自成一派;反之就归类到前面,这样可以使前面一派更大
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        vector<int> dp(n + 1);
        for(int i=1;i<=n;i++){
            if(dp[i - 1] < 0){
                dp[i] = a[i];
            }else{
                dp[i] = a[i] + dp[i - 1];
            }
        }
        int ans = -2e9;
        for(int i=1;i<=n;i++){
            ans = max(ans, dp[i]);
        }
        cout << ans; 
        return 0;
    }
    
    • 这里可以省掉这个 d p dp dp数组,边读边处理,因为满足无后效性,后面不会对前面产生影响

    m段连续最大子段和

    接下来是一道最大子段和的加强版
    http://acm.hdu.edu.cn/showproblem.php?pid=1024
    意思是从一个序列中找 m m m个连续子段,要求所有的总和最大的值是多少,这 m m m个子段随便找只要没有重叠部分即可

    • 和第一个问题相比,这个题要求找的子段确定了数量,所以考虑设 d p [ i ] [ j ] dp[i][j] dp[i][j]为前 i i i个数划分成以 i i i为结尾的 j j j个子段得到的最大总和,现在考虑第 i i i个数,如果说这个数划分到第 j j j段,那么应该有 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + a [ i ] dp[i][j]=dp[i-1][j]+a[i] dp[i][j]=dp[i1][j]+a[i];为什么是从 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]转移过来的?这是因为 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i1][j1]是表示以 a [ i − 1 ] a[i-1] a[i1]为结尾的划分成 j − 1 j-1 j1组的最大值, d p [ i ] [ j ] dp[i][j] dp[i][j]不可能从它转移过来,只能从 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]转移过来;那么如果这个数没有被划分到第 j j j段,那么前面的 i − 1 i-1 i1个数应该被划分为 j − 1 j-1 j1组,哪些数被划分?不知道,但是至少要有 j − 1 j-1 j1个数,最多 i − 1 i-1 i1个数,所以现在状态转移方程应该是 d p [ i ] [ j ] = d p [ k ] [ j − 1 ] + a [ i ] , j − 1 ≤ k ≤ i − 1 dp[i][j]=dp[k][j-1]+a[i],j-1\leq k\leq i-1 dp[i][j]=dp[k][j1]+a[i],j1ki1,所以总的状态转移方程就是
      d p [ i ] [ j ] = m a x { d p [ i ] [ j ] , d p [ i − 1 ] [ j ] + a [ i ] , d p [ k ] [ j − 1 ] + a [ i ] } , j − 1 ≤ k ≤ i − 1 dp[i][j]=max\{dp[i][j],dp[i-1][j]+a[i],dp[k][j-1]+a[i]\},j-1\leq k\leq i-1 dp[i][j]=max{dp[i][j],dp[i1][j]+a[i],dp[k][j1]+a[i]},j1ki1
      程序如下
    while(cin >> m >> n){
    	vector<int> a(n + 1);
    	for(int i=1;i<=n;i++) cin >> a[i];
    	vector<vector<int> > dp(n + 1, vector<int> (m + 1));
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			for(int k=j-1;k<i;k++){
    				dp[i][j] = max({dp[i][j], dp[i - 1][j] + a[i], dp[k][j - 1] + a[i]});
    			}
    		}
    	}
    	int ans = INT_MIN;
    	for(int i=m;i<=n;i++){
    		ans = max(ans, dp[i][m]);
    	}
    	cout << ans << '\n';
    }
    
    • 但是这样时间复杂度是 O ( n 2 m ) O(n^2m) O(n2m)的,对于 1 e 6 1e6 1e6 n n n显然不行

    压时间

    考虑优化,式子中的 d p [ k ] [ j − 1 ] dp[k][j-1] dp[k][j1]是在找上一层的最大值,我们可以在上层遍历的时候就把它找到并用一个数组记录下来,这样可以压掉这一层 O ( n ) O(n) O(n)的遍历,优化如下

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int m, n;
    	while(cin >> m >> n){
    		vector<int> a(n + 1);
    		for(int i=1;i<=n;i++) cin >> a[i];
    		vector<vector<int> > dp(n + 1, vector<int> (m + 1));
    		vector<int> dp2(n + 1);
    		int val = INT_MIN;
    		for(int j=1;j<=m;j++){		
    			val = INT_MIN;
    			for(int i=j;i<=n;i++){
    				dp[i][j] = max({dp[i][j], dp[i - 1][j] + a[i], dp2[i - 1] + a[i]});
    				dp2[i - 1] = val;
    				val = max(dp[i][j], val);
    			}
    		}
    		cout << val << '\n';
    	}
    	return 0;
    }
    
    • 注意这里因为没有存储中间状态,不能保证答案的合法性,所以必须在中间更新答案,最后一次循环由于 j j j达到 m m m,这一次循环出来就是最终答案,如果最后更新, i i i需要从 m m m开始,因为最少需要 m m m个数才能构成 m m m
    • 但是没有给出 m m m的范围,所以这样超空间也不行

    压空间

    • 我们或许能够发现,方程中 j j j并没有什么作用,因为都是从前一个状态转移过来的,正序更新即可
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n, m;
        while(cin >> m >> n){
            vector<int> a(n + 1);
            vector<int> dp1(n + 1);
            vector<int> dp2(n + 1);
            for(int i=1;i<=n;i++) cin >> a[i];
            int val = INT_MIN;
            for(int i=1;i<=m;i++){
                val = INT_MIN;
                for(int j=i;j<=n;j++){
                    dp1[j] = max(dp1[j - 1] + a[j], dp2[j - 1] + a[j]);
                    dp2[j - 1] = val;
                    val = max(val, dp1[j]);
                }
            }
    		// int ans = INT_MIN;
            // for(int i=m;i<=n;i++){//如果如此统计答案,需要从m开始
    		// 	ans = max(ans, dp1[i]);
    		// }//也可,因为dp1[i]含义是前i个数以i结尾分成m组的最大和
    		cout << val << '\n';
        }
        return 0;
    }
    

    这样时间复杂度是 O ( n m ) O(nm) O(nm),空间复杂度是 O ( n ) O(n) O(n),这样就没什么问题了

    最大双子段和

    https://www.luogu.com.cn/problem/P2642
    在一个序列里面找到两段连续的子段,让它们加和最大,这两个子段不能连成一个子段

    • 这个问题和上一个问题有相似的地方,它可以拆解成单个子问题,也就是分别找两个最大子段和,让它们加和最大,所以一个比较明显的思路是,我哦们找一个前缀最大子段和,再找一个后缀最大子段和,从前到后枚举中间点,更新最大值,前缀和后缀是独立的,因为它们不相交,所以能够容易的写出程序
    • 但是需要注意的是最好单独考虑首尾,或者更新前后缀最大子段和的时候从2开始更新
    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin >> n;
        vector<ll> a(n + 1);
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        vector<ll> pre(n + 1), suff(n + 2);
        for(int i=1;i<=n;i++){
            if(pre[i - 1] > 0){
                pre[i] = pre[i - 1] + a[i];
            }else{
                pre[i] = a[i];
            }
        }
        for(int i=2;i<=n;i++) pre[i] = max(pre[i - 1], pre[i]);
        for(int i=n;i>=1;i--){
            if(suff[i + 1] > 0){
                suff[i] = suff[i + 1] + a[i];
            }else{
                suff[i] = a[i];
            }
        }
        for(int i=n-1;i>=1;i--) suff[i] = max(suff[i + 1], suff[i]);
        ll ans = pre[1] + suff[3];
        for(int i=2;i<n;i++){
            ans = max(ans, pre[i - 1] + suff[i + 1]);
        }
        cout << ans;
        return 0;
    }
    

    这是一种比较巧妙的方法,但是如果考虑到分成的段数增多,那就不行了,所以这种方法不具有普适性;但是这题和上一个分成 m m m段的又不一样,因为那个是随便分没有重叠即可,这个问题要求子段之间不能连成一个区域

    • 还有一种方法,设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示前 i i i个数分成 j j j组, k k k表示选不选第 i i i个数, k ∈ [ 0 , 1 ] k\in[0,1] k[0,1],那么状态转移方程应该是 d p [ i ] [ j ] [ 0 ] = m a x ( d p [ i − 1 ] [ j ] [ 0 ] , d p [ i − 1 ] [ j ] [ 1 ] ) dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]) dp[i][j][0]=max(dp[i1][j][0],dp[i1][j][1]) d p [ i ] [ j ] [ 1 ] = m a x ( d p [ i − 1 ] [ j − 1 ] [ 0 ] , d p [ i − 1 ] [ j ] [ 1 ] ) + a [ i ] dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+a[i] dp[i][j][1]=max(dp[i1][j1][0],dp[i1][j][1])+a[i]
    • 关于初始状态,显然首先需要全初始化为 − ∞ -\infty ,只有一个数的时候,如果分成一组,那么有 d p [ 1 ] [ 1 ] [ 1 ] = a [ 1 ] dp[1][1][1]=a[1] dp[1][1][1]=a[1],如果不分组,那么有 d p [ 1 ] [ 0 ] [ 0 ] = 0 dp[1][0][0]=0 dp[1][0][0]=0,所以程序如下
    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    const int MAXN = 1e6 + 5;
    ll dp[MAXN][3][3];
    int main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n;
    	cin >> n;
    	vector<ll> a(n + 1);
    	for(int i=1;i<=n;i++) cin >> a[i];
    	memset(dp, -0x3f, sizeof dp);
    	dp[1][1][1] = a[1];
    	dp[1][0][0] = 0;
    	for(int i=2;i<=n;i++){
    		for(int j=0;j<=2;j++){
    			dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
    			if(j > 0)
    			dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0]) + a[i];
    		}
    	}
    	ll ans = max(dp[n][2][0], dp[n][2][1]);
    	cout << ans;
    	return 0;
    }
    
    • 用上述方法,我们就能够求出 m m m段的最大子段和了

    环状最大子段和

    https://nanti.jisuanke.com/t/A2232
    最大子段和的环状版本

    • 对于一个环状序列,通常的做法是数组翻倍,但是对于这个问题,并不应该这样做,因为环状最大子段和要么越过边界,要么不越过边界,如果没有越过边界,那么求一个最大子段和即可,如果越过了边界,我们需要看什么时候最大,那么这显然求原序列的最小子段和即可,因为我们找到了最小子段和,只要计算出序列总和,那么剩下的部分加和肯定是最大的,打印方案都搞得定
    • 最小子段和和最大子段和是一个道理,所以很容易写出程序
    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    int main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n;
    	cin >> n;
    	vector<ll> a(n + 1);
    	ll sum = 0;
    	for(int i=1;i<=n;i++){
    		cin >> a[i];
    		sum += a[i];
    	}
    	vector<ll> dp1(n + 1), dp2(n + 1);
    	for(int i=1;i<=n;i++) dp1[i] = max(dp1[i - 1] + a[i], a[i]);
    	for(int i=2;i<=n;i++) dp1[i] = max(dp1[i - 1], dp1[i]);
    	for(int i=1;i<=n;i++) dp2[i] = min(dp2[i - 1] + a[i], a[i]);
    	for(int i=2;i<=n;i++) dp2[i] = min(dp2[i - 1], dp2[i]);
    	cout << max(dp1[n], sum - dp2[n]);
    	return 0;
    }
    

    环状最大双子段和

    https://www.luogu.com.cn/problem/P1121
    有下面这两种情况
    1 ◯ ∗ ∗ ∗ ∗ 1111 ∗ ∗ ∗ ∗ 22222 ∗ ∗ ∗ ∗ \text{\textcircled 1}****1111****22222**** 1111122222
    2 ◯ 111 ∗ ∗ ∗ ∗ 2222 ∗ ∗ ∗ ∗ ∗ ∗ 11111 \text{\textcircled 2}111****2222******11111 2111222211111

    • 第一种情况只需要跑一次前缀最大子段和和后缀最大子段和枚举断点即可;第二种情况求最小前缀子段和和最小后缀子段和,然后用总和减掉两段最小。这样的思路和环状最大子段和是一样的,但是这样有可能出现下面的情况
      1111 ∗ 222222111111 1111*222222111111 1111222222111111或者这样 111222222222221111 111222222222221111 111222222222221111
    • 在这两种情况下我们如果按照 2 ◯ \text{\textcircled 2} 2来进行,那么就有可能只取一个数或者不取数,这样肯定是不对的,那为什么会出现这两种情况呢?容易想到是因为只有一个正数或者没有正数,所以在这两种情况之下我们不讨论 2 ◯ \text{\textcircled 2} 2,只选择 1 ◯ \text{\textcircled 1} 1即可
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin >> n;
        vector<int> a(n + 1);
        int num = 0;
        int sum = 0;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            sum += a[i];
            if(a[i] > 0) num += 1;
        }
        function<int()> ask = [&](){
            int res = INT_MIN;
            vector<int> pre(n + 1), suff(n + 2);
            for(int i=1;i<=n;i++) pre[i] = max(pre[i - 1] + a[i], a[i]);
            for(int i=2;i<=n;i++) pre[i] = max(pre[i - 1], pre[i]);
            for(int i=n;i>=1;i--) suff[i] = max(suff[i + 1] + a[i], a[i]);
            for(int i=n-1;i>=1;i--) suff[i] = max(suff[i + 1], suff[i]);
            for(int i=1;i<n;i++){
                res = max(res, pre[i] + suff[i + 1]);
            }
            return res;
        };
        int ans = ask();
        if(num == 1 || num == 0){
            cout << ans;
            return 0;
        }
        for(int i=1;i<=n;i++) a[i] *= -1;
        ans = max(ans, ask() + sum);
        cout << ans;
        return 0;
    }
    
    更多相关内容
  • 最大子段和

    2018-03-25 22:28:54
    分别用三重循环,分治法和动态规划算法来解决最大子段和问题,并比较三个算法效率的差异。内含c++源代码和实验报告说明
  • 1.用分治算法求解最大子段和问题。要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时...
  • 【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
  • 【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
  • 最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
  • 最大子段和及其下标(分治算法) 这个是王晓东《计算机算法设计与分析》第58页到59页最大子段和分治算法改写成除计算最大子段和外还要记录最大字段和的起点与终点。
  • 简单易懂的一种求最大子段和的方法,希望能和大家一起讨论
  • 动态规划实例最大子段和,MATLAB编程,动态规划实例
  • 动态规划的方法求最大子段和,算法复杂度为O(n)
  • 最大子段和问题

    2022-05-09 18:32:55
    FIrst:无限制最大子段和问题 时间复杂度: #include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long f[N]; int main(){ int n; scanf("%d",&n); long long res=-0x3f3f3f3f3f3...

    FIrst:无限制最大子段和问题 时间复杂度:O(n)

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    long long f[N];
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	long long res=-0x3f3f3f3f3f3f3f3f;
    	for(int i=1;i<=n;i++){
    		long long x;
    		scanf("%lld",&x);
    		f[i]=max(f[i-1],(long long)0)+x;
    		res=max(res,f[i]);
    	}
    	printf("%lld\n",res);
    	
    	return 0 - 0;
    }

    Second:子段长度不大于m的最大子段和问题 时间复杂度:O(n)

    #include<bits/stdc++.h>
    using namespace std;
    const int N=3e5+10;
    int n,m;
    long long sum[N];
    
    int main(){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++){
            long long x;
            scanf("%lld",&x);
            sum[i]=x+sum[i-1];
        }
        deque<long long> q;
        q.push_back(0);
        long long res=-0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<=n;i++){
            while(q.size()&&i-q.front()>m) q.pop_front();
            res=max(res,sum[i]-sum[q.front()]);
            while(q.size()&&sum[q.back()]>=sum[i]) q.pop_back();
            q.push_back(i);
        }
        printf("%lld\n",res);
        
        return 0 - 0;
    }

     Third:长度不小于m的最长子段和问题 时间复杂度:O(n)

    #include<bits/stdC++.h>
    using namespace std;
    const int N=2e5+10;
    int sum[N],f[N],g[N];
    
    int main(){
    	int n,m;
    	scanf("%d %d",&n,&m);
    	for(int i=1;i<=n;i++){
    		int x;
    		scanf("%d",&x);
    		f[i]=max(f[i-1],0)+x;
    		sum[i]=sum[i-1]+x;
    	}
    	int res=-0x3f3f3f3f;
    	for(int i=1;i+m-1<=n;i++){
    		g[i]=max(f[i-1],0)+sum[i+m-1]-sum[i-1];
    		res=max(g[i],res);
    	}
    	printf("%d\n",res);
    	
    	return 0 - 0;
    }

    Foruth:环状最大子段和问题 时间复杂度:O(n)

     1.将序列倍长,就可以做一遍长度不大于m的最大子段和

     2.先正着求一遍最大子段和,考虑子段是否过端点,过端点就取反,然后求一个最小子段和,不过端点就没有影响。

    Fifth:环状最大两段子段和 时间复杂度:O(n) / O(n^2)

    O(n^2) 考虑破环成链,枚举破坏的断点O(n),在链上求最大两段子段和;维护一个f1[i]为以a[i]结尾的最大子段和,一个f2[i]为以a[i]开头的最大子段和;(其实就是倒着求一遍)复杂度;

    O(n) 对于答案可能有的所有情况,一种是有一段跨过了端点,另一种是没有跨过端点;所以可以先求一遍两段最大子段和,再对整个序列取反,再求一遍(这时其实就是求出两段的最小子段和,用总和减去后就是跨过端点的两段最大子段和),这时把两种情况取一个max

    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    int s[N],front[N],back[N];
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&s[i]);
    	memset(front,-0x3f,sizeof(front)); 
    	memset(back,-0x3f,sizeof(back));
    	int sum1=-2e9,sum2=-2e9,sum=0;
    	for(int i=1;i<=n;i++) front[i]=max(front[i-1],0)+s[i];
    	for(int i=1;i<=n;i++) front[i]=max(front[i-1],front[i]);
    	for(int i=n;i>=1;i--) back[i]=max(back[i+1],0)+s[i];
    	for(int i=n;i>=1;i--) back[i]=max(back[i+1],back[i]);
    	for(int i=1;i<n;i++) sum1=max(sum1,front[i]+back[i+1]);
    	int cnt=0;
    	for(int i=1;i<=n;i++){
    		if(s[i]>0) cnt++;
    	}
    	if(cnt<=1){
    		printf("%d\n",sum1);
    		return 0 - 0;
    	}
    	memset(front,-0x3f,sizeof(front));
    	memset(back,-0x3f,sizeof(back));
    	for(int i=1;i<=n;i++) sum+=s[i],s[i]=-s[i];
    	for(int i=1;i<=n;i++) front[i]=max(front[i-1],0)+s[i];
    	for(int i=1;i<=n;i++) front[i]=max(front[i-1],front[i]);
    	for(int i=n;i>=1;i--) back[i]=max(back[i+1],0)+s[i];
    	for(int i=1;i<n;i++) sum2=max(sum2,front[i]+back[i+1]);
    	sum2=sum+sum2;
    	int res=max(sum1,sum2);
    	printf("%d\n",res);
    	
    	return 0 - 0;
    }
    展开全文
  • 最大子段和java实现

    2012-07-18 15:27:01
    最大子段和用java实现,同时利用了动态规划和分治两种方法实现
  • @[TOC]java代码求解最大子段和问题 什么是最大子段和问题 给定一个数组(元素已知),元素由正整数,负整数两种元素组成,现在求该数组中从哪个位置到哪个位置对应元素所组成的子段和最大,这个子段和就叫做最大子段和...

    @[TOC]java代码求解最大子段和问题

    什么是最大子段和问题

    给定一个数组(元素已知),元素由正整数,负整数两种元素组成,现在求该数组中从哪个位置到哪个位置对应元素所组成的子段和最大,这个子段和就叫做最大子段和。

    分析问题(分治思想)

    最大子段和不是在“前半段”(a[0] ~ a[mid])就是在“后半段”a[mid+1] ~ a[a,length-1],要么就是由“前半段部分元素和后半段部分元素连接起来a[i] ~ a[j]所构成(其中i(从mid ~ 0),j(从mid+1) ~ (a.length -1);”
    就以数组a[] = {-1,3,2}为例
    就以a[] = {-1,3,2}为例
    前半段从-1 ~3 后半段从2 ~ 2(也就是它本身) DSZ就指的是前半段和后半段所连接的“累加和最大的”子段和
    之后我们可以判断这三个值的大小 从而得出当前数组的最大子段和

    发现捷径

    当数组长度为2时可以比较a,b,a+b三个数的大小 从而选出最大值即为最大子段和

    当数组长度大于2时 需递归调用方法将数组划分为长度等于2的小数组,逐步得到所要求数组的最大子段和。

    因为当将数组划分到长度等于2的时候对应的小长度数组的最大子段和可以轻松的求解出来,进而一步步向所求数组一步步靠拢进而得到最终的最大子段和。

    if(mid == 0){
    			x = a[0];
    			y = a[1];
    			z = x + y;
    			if(x > y){
    				max = x;
    			}
    			else max = y;
    			if(max > z){
    				max = max;
    			}
    			else {max = z;}
    		return max;
    		}
    

    定义一个DSZ方法,用于返回当前数组前半段和后半段连接所构成的“累加和最大的”子段和

    public static int DSZ(int a[]){
    		int mid = (a.length-1)/2;
    		int H = a.length;
    		int i,j,max,x,y,z,L,D;
    		if(H%2 != 0){
    			L = mid+1;
    			D = mid ;
    		}
    		else {
    			L = mid +1;
    			D = mid +1; 
    		}
    		int[] d = new int[L];
    		int[] e = new int[D];
    		for(max = 0,i = mid,j = 0;i >=0;i--,j++){
    			max += a[i];
    			d[j] = max;
    		}
    		for(max = 0,i = (mid+1),j = 0;i < a.length;i++,j++){
    			max += a[i];
    			e[j] = max;
    		}
    		x = mid - ZDS(d);           
    		y = mid +ZDS(e)+1;
    		for(max = 0,i = x;i <= y;i++){
    			max += a[i];
    		}
    		return max;
    	}
    

    定义ZDS(最大数)方法用于辅佐DSZ方法求出前半段和后半段“累加和最大”的子段和

    public static int ZDS(int a[]){
    		int max,i,j = 0;
    		for(i = 0,max = 0;i < a.length;i++){
    			if(max < a[i]){
    				max = a[i];
    			}
    		}
    		for(i = 0;i < a.length;i++){
    			if(max == a[i]){
    				j = i;
    			}
    		}
    	return j;
    	}
    

    排版方法

    方法大致排版

    import java.util.Scanner;
    public class ZDZD4{
    	public static void main(String[] args){
    		System.out.println("请输入数组元素并用逗号隔开:");
    		Scanner s1 = new Scanner(System.in);
    		String str = s1.next().toString();
    		String[] b = str.split(",");
    		int[] a = new int[b.length];
    		for(int j = 0;j < a.length;j++){
    			a[j] = Integer.parseInt(b[j]);
    			System.out.print(a[j]+" ");
    		}
    		System.out.println();
    		System.out.print("该数组的最大子段和为:"+ZDZD1(a));
    	}
    	public static int ZDZD1(int a[]){
    		int i,j,x,v,max,y = 0,z = 0,n = 0,m = 0,H,L,D,t,q;
    		int mid = (a.length-1) / 2;
    		int O = a.length;
    		if(O == 1){
    			return a[0];
    		}
    		else if(O%2 != 0){
    			L = mid+1;
    			D = mid ;
    		}
    		else{
    			L = mid +1;
    			D = mid +1; 
    		}
    		int[] b = new int[L];
    		int[] c = new int[D];
    		if(mid == 0){
    			x = a[0];
    			y = a[1];
    			z = x + y;
    			if(x > y){
    				max = x;
    			}
    			else max = y;
    			if(max > z){
    				max = max;
    			}
    			else {max = z;}
    		return max;
    		}
    		else {	
    			x = DSZ(a);
    			for(i = 0;i <= mid ;i++){
    				b[i] = a[i];
    			}
    			for(v = mid+1,j= 0;v < a.length;v++){
    				if(a[v] != 0){
    					c[j] = a[v];
    					j++;
    				}
    			}
    			n = ZDZD1(b);
    			m = ZDZD1(c);
    			if(n > m){
    				max = n;
    			}
    			else {max = m;}
    			if(max > x){
    				max = max;
    			}
    			else {max = x;}
    			return max;
    		}
    	}
    	public static int DSZ(int a[]){
    		int mid = (a.length-1)/2;
    		int H = a.length;
    		int i,j,max,x,y,z,L,D;
    		if(H%2 != 0){
    			L = mid+1;
    			D = mid ;
    		}
    		else {
    			L = mid +1;
    			D = mid +1; 
    		}
    		int[] d = new int[L];
    		int[] e = new int[D];
    		for(max = 0,i = mid,j = 0;i >=0;i--,j++){
    			max += a[i];
    			d[j] = max;
    		}
    		for(max = 0,i = (mid+1),j = 0;i < a.length;i++,j++){
    			max += a[i];
    			e[j] = max;
    		}
    		x = mid - ZDS(d);           
    		y = mid +ZDS(e)+1;
    		for(max = 0,i = x;i <= y;i++){
    			max += a[i];
    		}
    		return max;
    	}
    	public static int ZDS(int a[]){
    		int max,i,j = 0;
    		for(i = 0,max = 0;i < a.length;i++){
    			if(max < a[i]){
    				max = a[i];
    			}
    		}
    		for(i = 0;i < a.length;i++){
    			if(max == a[i]){
    				j = i;
    			}
    		}
    	return j;
    	}
    }
    
    展开全文
  • 子序列之和最大,即最大子段和问题(Maximum Interval Sum)(有时也称LIS) 子序列:[A1,A2,…,An] 的子序列: [Ai,Aj] ,其中i<=j, 1 <= i,j <= n 求和:[A1,A2,…,An] 求和 = A1 + A2 + … + An 举例 ...

    前言

    子序列之和最大,即最大子段和问题(Maximum Interval Sum)(有时也称LIS)

    子序列:[A1,A2,…,An] 的子序列: [Ai,Aj] ,其中i<=j, 1 <= i,j <= n

    求和:[A1,A2,…,An] 求和 = A1 + A2 + … + An

    举例

    数组:5 4 -1 7 8
    方案1:遍历,求sum值,然后比大小
    	5					sum = 5
    	5 4					sum = 9
    	5 4 -1				sum = 8
    	5 4 -1 7		    sum = 15
    	5 4 -1 7 8			sum = 23
    
    	  4					sum = 4
    	  4 -1				sum = 3
    	  4 -1 7			sum = 10
    	  4 -1 7 8			sum = 18
    	   
    		-1				sum = -1
    		-1 7			sum = 6
    		-1 7 8			sum = 14
    		   
    		   7			sum = 7
    		   7 8			sum = 15
    		   
    			 8			sum = 8
    
    改进方案1:
    	1. 每一次遍历都可以使用上次的计算值 + 下一个元素
    	2. i++ 就清零,需要重启计算

    方案1:穷举

    1. 第一层和第二层 是 进行穷举所有子序列

    2. 第三次是求 子序列的累加和

    	    public int maxSubArray2(int[] nums) {
    	    	if(nums == null || nums.length == 0){
    	    		return 0;
    	    	}
    	    	int len = nums.length;
    	    	if(len == 1){
    	    		return nums[0];
    	    	}
    	    	// 所有的和最大值,默认去第一个总不会错
    	    	int allSumMax = Integer.MIN_VALUE;
    	    	// 行最大值
    	    	int rowSumMax = 0;
    	    	int rowSum = 0;
    	    	/**
    	    	 * 既然是子序列,那么[-i----------j--] i和j就是在 [0,len]之间,i < j
    	    	 * i 从0开始,len-2结束。 len-1 即最后一个元素流给j
    	    	 * j 从i开始,len-1结束
    	    	 * 从编码看:如果
    	    	 */
    	    	for (int i = 0; i < len ; i++) {
    	    		rowSum = nums[i];
    	    		rowSumMax = nums[i];
    	    		for (int j = i + 1; j < len; j++) {
    	    			// 每次累计
    	    			rowSum += nums[j];
    	    			// 只有当前数值>0 才可能比原来积累的最大值大,当然也可以比原来的小,是中间添加了交大的负值
    	    			if(nums[j] > 0 && rowSum > rowSumMax){
    	    				rowSumMax = rowSum;
    	    			}
    	    		}
    	    		// 判断[i]子序列集合求和最大值 跟 最大值 之间的关系
    	    		if(rowSumMax > allSumMax){
    	    			allSumMax = rowSumMax;
    	    		}
    	    	}
    	    	return allSumMax;
    	    }

    方案2:对穷举中 求和的改进

     public int maxSubArray1(int[] nums) {
    	    	if(nums == null || nums.length == 0){
    	    		return 0;
    	    	}
    	    	int len = nums.length;
    	    	if(len == 1){
    	    		return nums[0];
    	    	}
    	    	int sum = Integer.MIN_VALUE;
    	    	int tempSum = 0;
    	    	/**
    	    	 * 既然是子序列,那么[-i----------j--] i和j就是在 [0,len]之间,i < j
    	    	 * i 从0开始,len-2结束。 len-1 即最后一个元素流给j
    	    	 * j 从i开始,len-1结束
    	    	 * 从编码看:如果
    	    	 */
    	    	for (int i = 0; i < len ; i++) {
    	    		for (int j = i; j < len; j++) {
    	    			// 求子序列之和 [i,j]
    	    			for (int k = i; k <= j; k++) {
    	    				tempSum += nums[k];
    	    			}
    	    			// 如果当前序列,比我原来的大,就记录值
    	    			if(tempSum > sum){
    	    				sum = tempSum;
    	    			}
    	    			tempSum = 0;
    	    		}
    	    	}
    	    	
    	    	return sum;
    	    }

    方案3:对其实最大值的改进

    思路: 想从这之间找到规律,不就可以遍历一次了。 

    问题:1. 编码很麻烦,需要处理特例很多。2. 如果最大值并没有参与运算,下列红框的max之间就没有关系了,也就从根子上没法做。

    补充方案:存储 不包含 第一个元素,如果5作为的单个序列的,其他子序列之和最大值,因为后边的最大值跟这个一定有关系。

    继续改进:
    [i]子序列集合:从上面可以看出i每遍历一个值,j就从i到length-1,形成了一个子序列集合。咱们就陈i子序列集合
    [i]子序列集合求和最大值:i子序列每个序列的求和后 比较出来的最大值
    1. 假如当前num[i] > 0 ; [i]子序列集合求和最大值 = [i+1]子序列集合求和最大值 + num[i] 
    2. 类似:num[i] = 0; [i]子序列集合求和最大值  = [i+1]子序列集合求和最大值
    3. 同理:num[i] < 0; [i]子序列集合求和最大值 + num[i]  = [i+1]子序列集合求和最大值 
    合并序列集合求和最大值:[i]子序列集合求和最大值  he [i+1]子序列集合求和最大值   合并为 [i,i+1]子序列集合求和最大值
    1. 假如当前num[i] > 0 ; [i]子序列集合求和最大值 就是 [i,i+1]子序列集合求和最大值
    2. 类似:num[i] = 0; [i]或者[i]子序列集合求和最大值 就是 [i,i+1]子序列集合求和最大值
    3. 同理:num[i] < 0; [i+1]子序列集合求和最大值 就是 [i,i+1]子序列集合求和最大值
    特例:
    1. 全是负数
    2. 收尾有包含0的元素,如:001100
    3. 元素为0和负数
    4. 如果最大值就是第一项,说明第一项就没有参与运算,[i] 和 [i+1]也就没关系了,也就不适用了。
        - 记录不包含 第一项的最大值,这条路走下去就沟里边了

    复制一个不怎么完善的代码,可以放在力扣中去执行,把特例第四项补充上,个人不建议做,一个算法补丁这么多,只能说刚开始的建模就有问题。

    class Solution {
    	    public int maxSubArray(int[] nums) {
    	    	if(nums == null || nums.length == 0){
    				return 0;
    			}
    			int len = nums.length;
    			if(len == 1){
    				return nums[0];
    			}
    			// 非0开始数组区间
    			int startIndex = 0;
    			for (int j = 0; j < len; j++) {
    				if(nums[j] != 0){
    					startIndex = j;
    					break;
    				}
    			}
    			int endIndex = 0;
    			for (int j = len - 1; j >= 0; j--) {
    				if(nums[j] != 0){
    					endIndex = j;
    					break;
    				}
    			}
    			// 全是0场景
    			if(startIndex == len || endIndex == -1){
    				return 0;
    			}
    			
    			// 所有的和最大值,默认去第一个总不会错
    			int allSumMax = Integer.MIN_VALUE;
    			// 计算 [0]子序列集合求和最大值
    			int rowSumMax = nums[startIndex];
    			int rowSum = nums[startIndex];
    			// 所有都是负值
    			boolean allNegativeData = nums[startIndex] <= 0;
    			int allNegativeMax = nums[startIndex] ;
    			for (int j = startIndex + 1; j <= endIndex; j++) {
    				// 每次累计
    				rowSum += nums[j];
    				// 只有当前数值>0 才可能比原来积累的最大值大,当然也可以比原来的小,是中间添加了交大的负值
    				if(nums[j] >= 0 && rowSum > rowSumMax){
    					rowSumMax = rowSum;
    				}
    				// 如果出现正数,就不在继续
    				if(nums[j] > 0 && allNegativeData){
    					allNegativeData = false;
    				}
    				// 求最大值
    				if(nums[j] > allNegativeMax){
    					allNegativeMax = nums[j]; 
    				}
    			}
    			// 解决全负数情况
    			if(allNegativeData){
    				// 前面还有0
    				if(startIndex > 0 || endIndex < len - 1){
    					return 0;
    				}
    				return allNegativeMax;
    			}
    			allSumMax = rowSumMax;
    			
    			// 遍历处理 [i+1]子序列集合求和最大值
    			for (int i = startIndex + 1; i <= endIndex ; i++) {
    				rowSumMax -= nums[i - 1];
    				
    				if(rowSumMax > allSumMax){
    					allSumMax = rowSumMax;
    				}
    			}
    			return allSumMax;
    	    }
    	}

    后面继续补充 最大子数组(序列)和的 其他实现方法

    展开全文
  • 1、经典的区间最大子段和问题 问题描述:给定一个序列a1,a2,a3,..ana_1,a_2, a_3,..a_na1​,a2​,a3​,..an​,如何求出该序列的最大子段和?(询问的区间个数为mmm) 解决方案: - 暴力统计:对于每一个区间[l,r]...
  • 【动态规划】最大子段和 1??问题引入(恒生电子笔试题) 2??问题描述 3??两种设计方法 穷举法 动态规划法 4??升级版最大字段和 1问题引入(恒生电子笔试题) 输入一个整型数组,数组里有正数也有负数。数组...
  • 算法设计之最大子段和 问题描述 给n个整数序列,求出该序列的最大子段和序列。 输出C[1],C[2]…及l[1],l[2],l[3]…e[1],e[2],e[3]…的计算过程,并给出最终解。 的分治算法,递归的实现过程也写出来验证一下结果。 ...
  • 这里的背景色是:Aquamarine, 十六进制颜色值:#7FFFD4, rgb(127, 255, 212) 问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和最大值。当所给的整数均为...
  • 给定由n个整数组成的序列(a1, a2, …, an),最大子段和问题要求该序列形如∑ak (i <= k <= j) 的最大值(1≤i≤j≤n)。 当序列中所有整数均为负整数时,定义最大子段和为0。例如,序列(-20, 11, -4, 13, -5, ...
  • 动态规划解最大子段和问题

    千次阅读 2020-11-16 10:58:51
    选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间 2 最大子段和问题描述 给定n个整数(可能为负数)组成的序列a1,a2,…,an。求该序列形如下式的子段和的...
  • 最大子段和算法详解

    2021-05-21 16:27:14
    先介绍一下什么是最大子段和:确定每个子段和开始的位置,分别为第一个,第二个,第三个…第N个,然后计算从这个位置开始到这个位置之后的每个位置的子段和,更新记录最大的子段和。简单来讲有个数组属于实数,连续...
  • 最大子段和C语言实现

    2022-03-27 17:05:00
    C++代码实现 方法有循环穷举法,分治法,前缀法,动态规划法
  • 将长度为n的序列L划分成两个子序列,即 L(1,n/2) L(n/2 + 1 ,n)会出现3种情况:① max{ L(1,n) }=max{ L(1,n/2)}② max{ L(1,n) }=max{ L(n/2 + 1 ,n) }③max{ L(1,n) } = 且求解子问题:对于划分阶段的...
  • 最大子段和 题目描述 给出一个长度为 nn 的序列 aa,选出其中连续且非空的一段使得这段和最大。 输入格式 第一行是一个整数,表示序列的长度 nn。 第二行有 nn 个整数,第 ii 个整数表示序列的第 ii 个数字...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,127
精华内容 5,650
关键字:

最大子段和

友情链接: Beyond-CMOS.rar