元素和最大的子矩陣

題目描述

輸入一個(gè)n級方陣，請找到此矩陣的一個(gè)子矩陣，此子矩陣的各個(gè)元素的和是所有子矩陣中最大的，輸出這個(gè)子矩陣及這個(gè)最大的和。

關(guān)于輸入

首先輸入方陣的級數(shù)n，
然后輸入方陣中各個(gè)元素。

關(guān)于輸出

輸出子矩陣，
最后一行輸出這個(gè)子矩陣的元素的和。

例子輸入

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

例子輸出

9 2
-4 1
-1 8
15

解題分析

這個(gè)程序是一個(gè)求解最大子矩陣和的問題。可以使用動(dòng)態(tài)規(guī)劃和Kadane算法。這個(gè)問題可以描述為：給定一個(gè)二維數(shù)組，找出其中的一個(gè)子矩陣，使得這個(gè)子矩陣中所有元素的和最大。

這個(gè)程序的主要思路如下：

1. 讀取一個(gè)整數(shù)`n`，然后讀取一個(gè)`n`x`n`的整數(shù)矩陣`a`。

2. 計(jì)算`total`數(shù)組，`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. 遍歷所有可能的子矩陣。對于每一個(gè)子矩陣，計(jì)算其元素之和，然后與當(dāng)前最大的子矩陣和進(jìn)行比較。如果新的子矩陣和更大，就更新最大的子矩陣和，以及對應(yīng)的子矩陣的左上角和右下角的坐標(biāo)。

4. 在計(jì)算子矩陣和的過程中，使用了Kadane算法。Kadane算法可以在O(n)的時(shí)間復(fù)雜度內(nèi)求解最大子數(shù)組和的問題。在這個(gè)程序中，Kadane算法被用來求解每一行元素之和的最大值。

5. 最后，打印出最大子矩陣和，以及對應(yīng)的子矩陣的元素。

Kadane算法是一個(gè)用于解決最大子數(shù)組和問題的動(dòng)態(tài)規(guī)劃算法。最大子數(shù)組和問題可以描述為：在一個(gè)一維數(shù)組中，找出一個(gè)連續(xù)的子數(shù)組，使得這個(gè)子數(shù)組中所有元素的和最大。

Kadane算法的基本思想是，對于數(shù)組中的每個(gè)位置，計(jì)算以該位置為結(jié)束點(diǎn)的所有子數(shù)組中，和最大的那個(gè)子數(shù)組的和。然后，從這些和中找出最大的那個(gè)，就是最大子數(shù)組和。

具體來說，算法的步驟如下：

1. 初始化兩個(gè)變量，`max_so_far`和`max_ending_here`，都設(shè)為數(shù)組的第一個(gè)元素。`max_so_far`表示到目前為止找到的最大子數(shù)組和，`max_ending_here`表示以當(dāng)前位置為結(jié)束點(diǎn)的子數(shù)組的最大和。

2. 對于數(shù)組中的每個(gè)位置，首先計(jì)算`max_ending_here + array[i]`，然后與`array[i]`比較，取較大的那個(gè)作為新的`max_ending_here`。這一步表示，如果加上當(dāng)前元素能使子數(shù)組和更大，就加上當(dāng)前元素，否則就從當(dāng)前元素開始新的子數(shù)組。

3. 然后，比較`max_so_far`和`max_ending_here`，取較大的那個(gè)作為新的`max_so_far`。這一步表示，如果`max_ending_here`比`max_so_far`大，就更新`max_so_far`。

4. 重復(fù)上述步驟，直到遍歷完數(shù)組。

5. 最后，`max_so_far`就是最大子數(shù)組和。

Kadane算法的時(shí)間復(fù)雜度是O(n)，因?yàn)樗恍枰闅v一次數(shù)組。這使得它在處理大規(guī)模數(shù)據(jù)時(shí)非常高效。

舉個(gè)例子：

讓我們通過一些具體的例子來理解Kadane算法。

假設(shè)我們有一個(gè)數(shù)組`{-2, -3, 4, -1, -2, 1, 5, -3}`，我們想找到這個(gè)數(shù)組中，和最大的子數(shù)組。

我們可以按照Kadane算法的步驟來操作：

1. 初始化`max_so_far`和`max_ending_here`為數(shù)組的第一個(gè)元素`-2`。

2. 對于數(shù)組中的第二個(gè)元素`-3`，我們先計(jì)算`max_ending_here + array[i]`，得到`-2 - 3 = -5`，然后與`-3`比較，取較大的那個(gè)作為新的`max_ending_here`，所以`max_ending_here`更新為`-3`。然后，比較`max_so_far`和`max_ending_here`，取較大的那個(gè)作為新的`max_so_far`，所以`max_so_far`保持不變，還是`-2`。

3. 對于數(shù)組中的第三個(gè)元素`4`，我們先計(jì)算`max_ending_here + array[i]`，得到`-3 + 4 = 1`，然后與`4`比較，取較大的那個(gè)作為新的`max_ending_here`，所以`max_ending_here`更新為`4`。然后，比較`max_so_far`和`max_ending_here`，取較大的那個(gè)作為新的`max_so_far`，所以`max_so_far`更新為`4`。

4. 以此類推，我們可以得到以下的結(jié)果：

?? ```
?? 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`就是最大子數(shù)組和，也就是`7`。這個(gè)最大和的子數(shù)組是`{4, -1, -2, 1, 5}`。

通過這個(gè)例子，我們可以看到，Kadane算法可以有效地找到最大子數(shù)組和，而且只需要遍歷一次數(shù)組。文章來源地址http://www.zghlxwxcb.cn/news/detail-779845.html

代碼實(shí)現(xiàn)

#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;
}

到了這里，關(guān)于[Kadane算法,前綴和思想]元素和最大的子矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！