最大子序和——最大子矩阵

清疚 2022-02-20 05:52 339阅读 0赞

# [LeetCode-最大子序和][LeetCode-] #

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

### 示例: ###

输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

### 动态规划 ###

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            vector<int> dp(nums.size(),0);
            int m=0,maxn=nums[0];
            for(int i=0;i<nums.size();i++)
            { 
                if(m>0) m+=nums[i]; //m是正数接着往上加
                else m=nums[i]; //m是负数那就不要再加了，因为负数会拉低nums[i]的数值
                maxn=max(maxn,m);
            }
            return maxn;
        }
    };

# [ZOJ-最大子矩阵][ZOJ-] #

### Description ###

给定一个n\*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

其中，A的子矩阵指在A中行和列均连续的一块。

### Input ###

输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。（1 ≤ n, m ≤ 500）

接下来n行，每行m个整数，表示矩阵A。

### Output ###

输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。

### Sample Input ###

3 3
    -1 -4 3
    3 4 -1
    -5 -2 8

### Sample Output ###

### 降维 动态规划 ###

枚举所有可能的组合情况，按列累加，转变成一维的求最大子序和问题

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <vector>
    using namespace std;
    int findMax(int *arr,int n)
    { 
        int maxn=arr[0],m=0;
        for(int i=0;i<n;i++)
        { 
            if(m>0) m+=arr[i];
            else m=arr[i];
            if(maxn<m) maxn=m;
        }
        return maxn;
    }
    int dp[505][505];
    int arr[505];
    int main()
    { 
        freopen("test.txt","r",stdin);
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        { 
            for(int j=0;j<m;j++)
            { 
                cin>>dp[i][j];
            }
        }
        //枚举所有组合情况
        int maxn=dp[0][0;
        for(int i=0;i<n;i++)
        { 
            fill(arr,arr+n,0);
            for(int j=i;j<m;j++)
            { 
                for(int k=0;k<n;k++)
                    arr[k]+=dp[k][j]; //累加k行j列
                int m=findMax(arr,n);
                maxn=max(m,maxn);
            }
        }
        cout<<maxn<<endl;
        return 0;
    }

前缀和+二维LIS

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <vector>
    using namespace std;
    int dp[505][505]; //dp[i][j]:j列前i行的前缀和
    int n, m;
    const int INF = 0x3f3f3f3f;
    int main()
    { 
        // freopen("test.txt","r",stdin);
        cin >> n >> m;
        int maxSum = -INF;
        bool flag = false;
        for (int i = 1; i <= n; i++)
        { 
            for (int j = 1; j <= m; j++)
            { 
                cin >> dp[i][j];
                if (dp[i][j] < 0)
                { 
                    maxSum = max(maxSum, dp[i][j]);
                }
                else
                    flag = true; //不全负
                dp[i][j] += dp[i - 1][j];
            }
        }
        if (flag == false)
            cout << maxSum << endl;
        else
        { 
            int ans = 0;
            for (int i = 1; i <= n; i++) //枚举所有可能的组合
            { 
                for (int j = i; j <= n; j++)
                { 
                    int maxn = 0;
                    for (int k = 1; k <= m; k++)
                    { 
                        maxn += (dp[j][k] - dp[i - 1][k]);
                        if (maxn < 0)
                            maxn = 0;
                        ans = max(maxn, ans);
                    }
                }
            }
            cout << ans << endl;
        }
        return 0;
    }

[LeetCode-]: https://leetcode-cn.com/problems/maximum-subarray/
[ZOJ-]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1074