连续子数组的最大和（一维）

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

题解

class Solution {
          
   
public:
    int maxSubArray(vector<int>& nums) {
          
   
        int res = -1100;
        int h;
        int a[1010] = {
          
   0};
        for (int i = 0 ; i < nums.size() ; i ++){
          
   
            h = max(h, 0) + nums[i];
            res = max(res, h);
        }
        return res;
    }
};

关键点：当前缀和为负数的时候，就清空为0，然后在上一个循环（前缀和大于0的最后一次）的时候看看要不要更新一下最后的结果 或者另一个角度，就是先分一段一段（是取大于0的段），然后更新最高端作为结果输出。

最大的和（二维）

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中，具有最大和的子矩形被称为最大子矩形。

例如，下列数组：

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2

其最大子矩形为：

9 2 
-4 1 
-1 8

它拥有最大和15。

输入格式

输入中将包含一个N*N的整数数组。

第一行只输入一个整数N，表示方形二维数组的大小。

从第二行开始，输入由空格和换行符隔开的N2N2个整数，它们即为二维数组中的N2N2个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。

数组中的数字会保持在[-127,127]的范围内。

输出格式

输出一个整数，代表最大子矩形的总和。

数据范围

1≤N≤1001≤N≤100

输入样例：

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

输出样例：

15

题解

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int s[N][N];
int n;
int res = -300;
int main(){
          
   
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
          
   
        for (int j = 1; j <= n; j ++ ){
          
   
            int x;
            cin >> x;
            s[i][j] = s[i - 1][j] + x;
        }
    }
    
    for (int i = 1; i <= n; i ++ ){
          
   
        for (int j = i; j <= n; j ++){
          
   
            int f = 0;
            for (int k = 1; k <= n; k++ ){
          
   
                int w = s[j][k] - s[i - 1][k];
                f = max(f, 0) + w;
                res = max(res, f);
            }
        }
    }
    cout << res;
    return 0;
}

第一步是准备好竖直方向的前缀和，目的是在后面的处理中把中间某一段竖直方向的和作为一个数！！！！ 第二步是：先选定两行（遍历），然后把两行之间的数作为一行数，于是就变成了一维问题