子矩阵的最大累加和问题

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define max(a,b) ((a) > (b) ? (a) : (b))

int main(void) {
    int n, m, **matrix;
    scanf("%d%d", &n, &m);
    matrix = (int **) malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        matrix[i] = (int *) malloc(m * sizeof(int));
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    
    int *help, pre, maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        help = (int *) calloc(m, sizeof(int));
        for (int j = i; j < n; j++) {
            pre = 0;
            for (int k = 0; k < m; k++) {
                help[k] += matrix[j][k];
                pre = help[k] + pre;
                maxSum = max(maxSum, pre);
                pre = pre < 0 ? 0 : pre;
            }
        }
    }
    printf("%d\n", maxSum);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m,n;
    cin>>m>>n;
    int a[m][n], b[n], s=INT_MIN;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    for(int i=0;i<m;i++){
        memset(b, 0, sizeof(b));
        for(int j=i;j<m;j++){
            for(int k=0;k<n;k++)
                b[k] += a[j][k];
            for(int k=0,t=0;k<n;k++){
                if(k==0 || t<0)
                    t = b[k];
                else
                    t += b[k];
                s = max(s, t);
            }
        }
    }
    cout<<s<<endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        int[] s = null;
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            s = new int[matrix[0].length];
            for (int j = i; j < matrix.length; j++) {
                cur = 0;
                for (int k = 0; k < matrix[0].length; k++) {
                    s[k] += matrix[j][k];
                    cur += s[k];
                    max = Math.max(max, cur);
                    if (cur < 0) {
                        cur = 0;
                    }
                }
            }
        }
        System.out.println(max);
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int row = sc.nextInt();
        int col = sc.nextInt();
        int[][] m = new int[row][col];
        for(int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                m[i][j] = sc.nextInt();
            }
        }
        System.out.println(getMaxSum(m));
        sc.close();
    }
    
    //本题主旨在通过把多行合并和一列数组，然后再本列数组中找最大累加和从而得到结果
    //比方说合并第一行与第二行时，含义为，限定子矩阵必须为两行（第一行与第二行）时，
    //最大累加和是多少，以此类推，把所有可能都找个遍即可
    public static int getMaxSum(int[][] m) {
        if (m == null || m[0] == null || m.length == 0 || m[0].length == 0)
            return 0;
        int max = Integer.MIN_VALUE;
        int[] tmp = null;
        int cur = 0;
        for (int i = 0; i < m.length; i++) {
            tmp = new int[m[0].length];
            for (int j = i; j < m.length; j++) {
                cur = 0;
                //在一个数组中找最大累加和的做法
                for (int k = 0; k < m[0].length; k++) {
                    tmp[k] += m[j][k];
                    cur += tmp[k];
                    max = Math.max(max, cur);
                    //无论接下来的数是正是负，都没必要多加上一个负的累加和
                    cur = cur < 0 ? 0 : cur;
                }
            }
        }
        return max;
    }
}

import java.util.Scanner;

public class Main {
    private static int maxSubArraySum(int[] arr) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            sum += num;
            max = Math.max(max, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }

    private static int maxSubMatrixSum(int[][] matrix) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            int[] array = matrix[i];
            max = Math.max(max, maxSubArraySum(array));
            for (int k = 1; i + k < matrix.length; k++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    array[j] += matrix[i + k][j];
                }
                max = Math.max(max, maxSubArraySum(array));
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        int res = maxSubMatrixSum(matrix);
        System.out.println(res);
    }
}

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = bf.readLine().split(" ");
        int n = Integer.valueOf(str1[0]), m = Integer.valueOf(str1[1]);
        int[][] arr = new int[n][m];
        String[] str2;
        for (int i = 0; i < n; i++) {
            str2 = bf.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.valueOf(str2[j]);
            }
        }
        bf.close();

        int[] temp;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            temp = new int[m];
            for (int j = i; j >= 0; j--) {
                for (int k = 0; k < m; k++) {
                    temp[k] += arr[j][k];
                }
                max = Math.max(max, helper(temp));
            }
        }
        System.out.println(max);
    }

    public static int helper(int[] temp) { // 计算一维数组的子数组的最大累加和，当然可以写入上面三层for循环中的最内层for循环
        int sum = 0, max = 0;
        for (int i = 0; i < temp.length; i++) {
            if (sum >= 0) {
                sum += temp[i];
            } else {
                sum = temp[i];
            }
            max = Math.max(max, sum);
        }
        return max;
    }
}

#include<cstdio>
(802)#include<algorithm>
using namespace std;
int v[210][210];
int r[210];
int n,m;
int ssum(){
    int mmax,dp;
    dp=r[0];
    mmax=r[0];
    for(int i=1;i<m;++i){
        dp=dp<0?r[i]:(dp+r[i]);
        mmax=max(mmax,dp);
    }
    return mmax;
}
int main(){
     scanf("%d %d",&n,&m);
     for(int i=0;i<n;++i){
         for(int j=0;j<m;++j){
             scanf("%d",&v[i][j]);
         }
     }
    int maxsum=-110;
    for(int i=0;i<n;++i){
        fill(r,r+m,0);
        for(int j=i;j<n;++j){
            for(int k=0;k<m;++k){
                r[k]+=v[j][k];
            }
            maxsum=max(maxsum,ssum());
        }
    }
    printf("%d",maxsum);
    return 0;
}