最大子列和+最大子矩阵和

一、最大子列和问题

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

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

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

输入样例:
6
-2 11 -4 13 -5 -2

输出样例:
20

1.普通遍历一遍

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e6+10;
int a[N],ans;
signed main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    int i=1;
    while (a[i]<=0&&i<=n) i++;
    int sum=0;
    while (i<=n)
    {
        while (a[i]>=0&&i<=n) sum +=a[i],i++;
        ans=max(ans,sum);
        while (a[i]<0&&i<=n) sum +=a[i],i++;
    }
    ans=max(ans,sum);
    cout<<ans;
    return 0;
}

2.DP

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e6+10;
int d[N],ans;
signed main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        d[i]=max(d[i-1]+x,x);
        ans=max(ans,d[i]);
    }
    cout<<ans;
    return 0;
}

二、最大子矩阵和问题

最大子矩阵和问题。给定m行n列的整数矩阵A，求矩阵A的一个子矩阵，使其元素之和最大。

输入格式:
第一行输入矩阵行数m和列数n（1≤m≤100，1≤n≤100），再依次输入m×n个整数。

输出格式:
输出最大子矩阵各元素之和。

输入样例:
5 6
60 3 -65 -92 32 -70
-41 14 -38 54 2 29
69 88 54 -77 -46 -49
97 -32 44 29 60 64
49 -48 -96 59 -52 25

输出样例:
321

1.暴力搜索(找到每个左上角，每个右上角)   不过会超时哦！！！

#include <bits/stdc++.h>
using namespace std;
const int N=500;
int s[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    {
        int x;
        cin>>x;
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
    }
    int ans=-2e9;
    for (int x1=1;x1<=n;x1++)
    for (int y1=1;y1<=m;y1++)
    for (int x2=x1;x2<=n;x2++)
    for (int y2=y1;y2<=m;y2++)
    {
        int t=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
        ans=max(ans,t);
    }
    cout<<ans<<endl;
    return 0;
}

2.DP

#include <bits/stdc++.h>
using namespace std;
const int N=1001;
#define int long long
int a[N][N],f[N],d[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    {
        cin>>a[i][j];
        a[i][j] +=a[i-1][j];
    }
    int ans=-2e9;
    for (int i=1;i<=n;i++)
    for (int k=1;k<=i;k++)
    {
        memset(f,0,sizeof f);
        memset(d,0,sizeof d);
        for (int j=1;j<=m;j++)
        {
            f[j]=a[i][j]-a[i-k][j];
            d[j]=max(d[j-1]+f[j],f[j]);
            ans=max(ans,d[j]);
        }
    }
    cout<<ans;
    return 0;
}