[Kadane算法,前缀和思想]元素和最大的子矩阵

元素和最大的子矩阵

题目描述

输入一个n级方阵，请找到此矩阵的一个子矩阵，此子矩阵的各个元素的和是所有子矩阵中最大的，输出这个子矩阵及这个最大的和。

关于输入

首先输入方阵的级数n，
然后输入方阵中各个元素。

关于输出

输出子矩阵，
最后一行输出这个子矩阵的元素的和。

例子输入

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

例子输出

9 2
-4 1
-1 8
15

解题分析

这个程序是一个求解最大子矩阵和的问题。可以使用动态规划和Kadane算法。这个问题可以描述为：给定一个二维数组，找出其中的一个子矩阵，使得这个子矩阵中所有元素的和最大。

这个程序的主要思路如下：

1. 读取一个整数`n`，然后读取一个`n`x`n`的整数矩阵`a`。

2. 计算`total`数组，`total[i][j]`表示从`a[0][j]`到`a[i][j]`的元素之和。如果`i`为0，`total[i][j]`就等于`a[i][j]`，否则`total[i][j]`就等于`total[i-1][j]+a[i][j]`。

3. 遍历所有可能的子矩阵。对于每一个子矩阵，计算其元素之和，然后与当前最大的子矩阵和进行比较。如果新的子矩阵和更大，就更新最大的子矩阵和，以及对应的子矩阵的左上角和右下角的坐标。

4. 在计算子矩阵和的过程中，使用了Kadane算法。Kadane算法可以在O(n)的时间复杂度内求解最大子数组和的问题。在这个程序中，Kadane算法被用来求解每一行元素之和的最大值。

5. 最后，打印出最大子矩阵和，以及对应的子矩阵的元素。

Kadane算法是一个用于解决最大子数组和问题的动态规划算法。最大子数组和问题可以描述为：在一个一维数组中，找出一个连续的子数组，使得这个子数组中所有元素的和最大。

Kadane算法的基本思想是，对于数组中的每个位置，计算以该位置为结束点的所有子数组中，和最大的那个子数组的和。然后，从这些和中找出最大的那个，就是最大子数组和。

具体来说，算法的步骤如下：

1. 初始化两个变量，`max_so_far`和`max_ending_here`，都设为数组的第一个元素。`max_so_far`表示到目前为止找到的最大子数组和，`max_ending_here`表示以当前位置为结束点的子数组的最大和。

2. 对于数组中的每个位置，首先计算`max_ending_here + array[i]`，然后与`array[i]`比较，取较大的那个作为新的`max_ending_here`。这一步表示，如果加上当前元素能使子数组和更大，就加上当前元素，否则就从当前元素开始新的子数组。

3. 然后，比较`max_so_far`和`max_ending_here`，取较大的那个作为新的`max_so_far`。这一步表示，如果`max_ending_here`比`max_so_far`大，就更新`max_so_far`。

4. 重复上述步骤，直到遍历完数组。

5. 最后，`max_so_far`就是最大子数组和。

Kadane算法的时间复杂度是O(n)，因为它只需要遍历一次数组。这使得它在处理大规模数据时非常高效。

举个例子：

让我们通过一些具体的例子来理解Kadane算法。

假设我们有一个数组`{-2, -3, 4, -1, -2, 1, 5, -3}`，我们想找到这个数组中，和最大的子数组。

我们可以按照Kadane算法的步骤来操作：

1. 初始化`max_so_far`和`max_ending_here`为数组的第一个元素`-2`。

2. 对于数组中的第二个元素`-3`，我们先计算`max_ending_here + array[i]`，得到`-2 - 3 = -5`，然后与`-3`比较，取较大的那个作为新的`max_ending_here`，所以`max_ending_here`更新为`-3`。然后，比较`max_so_far`和`max_ending_here`，取较大的那个作为新的`max_so_far`，所以`max_so_far`保持不变，还是`-2`。

3. 对于数组中的第三个元素`4`，我们先计算`max_ending_here + array[i]`，得到`-3 + 4 = 1`，然后与`4`比较，取较大的那个作为新的`max_ending_here`，所以`max_ending_here`更新为`4`。然后，比较`max_so_far`和`max_ending_here`，取较大的那个作为新的`max_so_far`，所以`max_so_far`更新为`4`。

4. 以此类推，我们可以得到以下的结果：

?? ```
?? i = 3, array[i] = -1, max_ending_here = 3, max_so_far = 4
?? i = 4, array[i] = -2, max_ending_here = 1, max_so_far = 4
?? i = 5, array[i] = 1, max_ending_here = 2, max_so_far = 4
?? i = 6, array[i] = 5, max_ending_here = 7, max_so_far = 7
?? i = 7, array[i] = -3, max_ending_here = 4, max_so_far = 7
?? ```

5. 最后，我们得到的`max_so_far`就是最大子数组和，也就是`7`。这个最大和的子数组是`{4, -1, -2, 1, 5}`。

通过这个例子，我们可以看到，Kadane算法可以有效地找到最大子数组和，而且只需要遍历一次数组。

代码实现

#include <iostream>
using namespace std;

int a[1000][1000];
int total[1000][1000];
int result[1000];
int n;

int getmax(int &start,int &end){
    int local_start=0;
    int maxSum=result[0];
    int cur_max=result[0];
    for(int i=1;i<n;i++){
        if(result[i]>cur_max+result[i]){
            cur_max=result[i];
            local_start=i;
        }
        else{
            cur_max+=result[i];
        }
        if(cur_max>maxSum){
            start=local_start;
            end=i;
            maxSum=cur_max;
        }
    }
    return maxSum;
}

int main() {
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(i==0) total[i][j]=a[i][j];
            else total[i][j]=total[i-1][j]+a[i][j];
        }
    int top=0,bottom=0,left=0,right=0;
    int maxSum=total[0][0];
    for(int i=0;i<n;i++)
        for(int j=i;j<n;j++){
            int start=0,end=0;
            for(int k=0;k<n;k++){
                if(i==0){
                    result[k]=total[j][k];
                }
                else{
                    result[k]=total[j][k]-total[i-1][k];
                }
            }
            int sum=getmax(start,end);
            if(sum>maxSum){
                maxSum=sum;
                top=i; bottom=j; left=start; right=end;
            }
        }
    for(int i=top;i<=bottom;i++)
        for(int j=left;j<=right;j++){
            cout<<a[i][j];
            if(j!=right) cout<<" ";
            else cout<<endl;
        }
    cout<<maxSum<<endl;
	return 0;
}