zzoce 🧊
最大连续子序列和

最大连续子序列和

Fri Oct 04 2024
zzcoe
3 分钟
数据结构与算法 算法
278 字

算法竞赛进阶指南 P53[[算法笔记/数据结构/单调队列]]求最大子序和

P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CPP
1
2
3
4
5
6
7
8
9
10
11
long long int ans=1;  
ans=ans<<63;//ans=-9223372036854775808
int l=1,r=1;  
q[1]=0;  
for (int i=1;i<=n;i++){  
    while (l<=r&&q[l]<i-t)l++;//t为最大子序列长度，若题目没有要求即t==n（序列长度），不可省略。  
    ans=max(ans,sum[i]-sum[q[l]]);  //sum[i]是前缀和
    while (l<=r&&sum[q[r]]>=sum[i])r--;  
    q[++r]=i;  
}  
cout<<ans;

最大子矩阵和 求最大子矩阵和，思路：将矩阵压缩为一维线性关系，问题变为求最大子段和 P1719 最大加权矩形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>  
#include <cstring>  
#include <cmath>  
using namespace std;  
int b[130],a[130];  
int sum[130][130];  
int main ()  
{  
    int n;  
    cin>>n;  
    memset(a,0,sizeof (a));  
    //矩阵压缩。  
    for (int i=1;i<=n;i++){  
        for (int j=1;j<=n;j++){  
            cin>>sum[i][j];  
            sum[i][j]=sum[i][j]+sum[i-1][j];  
        }  
    }  
    //转化为求一维的最大子段和  
    int MAX=-1;  
    int ans=1;  
    int l=1,r=1;  
    int q[150];  
    MAX=MAX<<31;  
    for (int i=0;i<n;i++){  
        for (int j=i+1;j<=n;j++){  
            //求子矩阵的压缩：1行，1-2行，1-3行，2行，2-3行，3.。。  
            memset(a,0,sizeof (a));  
            memset(b,0,sizeof (b));  
            for (int k=1;k<=n;k++){  
                b[k]=sum[j][k]-sum[i][k];  
                a[k]=a[k-1]+b[k];  
            }  
            //求一维的最大子段和  
            ans=ans<<31;//ans=-9223372036854775808  
            q[1]=0;  
            for (int t=1;t<=n;t++){  
                while (l<=r&&q[l]<t-n)l++;  
                ans = max(ans,a[t]-a[q[l]]);  
                while (l<=r&&a[q[r]]>=a[t])r--;  
                q[++r]=t;  
            }  
            MAX=max(MAX,ans);  
        }  
    }  
    cout<<MAX<<endl;  
    return 0;  
}