《程序员代码面试指南》第八章数组和矩阵问题子矩阵的最大累加和问题-白红宇

《程序员代码面试指南》第八章数组和矩阵问题子矩阵的最大累加和问题

阅读量：6446 次

发布时间：2019-06-23

本文共 1111 字，大约阅读时间需要 3 分钟。

题目

子矩阵的最大累加和问题

java代码

package com.lizhouwei.chapter8;/** * @Description: 子矩阵的最大累加和问题 * @Author: lizhouwei * @CreateDate: 2018/5/8 21:33 * @Modify by: * @ModifyDate: */public class Chapter8_17 {    public int maxSum(int[][] matrix) {        int curSum = 0;        int maxSum = Integer.MIN_VALUE;        int[] help = new int[matrix[0].length];        for (int i = 0; i < matrix.length; i++) {            curSum=0;            for (int j = 0; j < matrix[0].length; j++) {                help[j] = help[j] + matrix[i][j];                curSum = curSum + help[j];                maxSum = Math.max(maxSum, curSum);                curSum = curSum < 0 ? 0 : curSum;            }        }        return maxSum;    }    //测试    public static void main(String[] args) {        Chapter8_17 chapter = new Chapter8_17();        int[][] matrix = {
   {-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}};        System.out.print("矩阵 matrix = {
   {-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}}最大累加和为:");        int res = chapter.maxSum(matrix);        System.out.print(res);    }}