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

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/209908.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/209908.shtml
英文地址,請注明出處:http://en.pswp.cn/news/209908.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

車載藍牙音樂流程簡單分析

關鍵類&#xff1a; /packages/apps/Bluetooth/src/com/android/bluetooth/avrcpcontroller/AvrcpControllerStateMachine.java /packages/apps/Bluetooth/src/com/android/bluetooth/avrcpcontroller/AvrcpControllerService.java 一、音樂播放狀態 CPP中通過JNI接口將接從…

Python中利用遺傳算法探索迷宮出路

更多資料獲取 &#x1f4da; 個人網站&#xff1a;ipengtao.com 當處理迷宮問題時&#xff0c;遺傳算法提供了一種創新的解決方案。本文將深入探討如何運用Python和遺傳算法來解決迷宮問題。迷宮問題是一個經典的尋路問題&#xff0c;尋找從起點到終點的最佳路徑。遺傳算法是一…

ActiveMQ斷線重連技巧,即通信高可用的配置

最近在做一個內部應用的時候&#xff0c;應用到了ActiveMQ作為服務之間消息傳遞&#xff0c;解耦服務之間的關聯&#xff0c;但是在應用的過程中遇到了連接斷線無法重連的問題&#xff0c;下面基于這個問題&#xff0c;深入了解一下ActiveMQ的一些相關原理和知識。 一、前置知…

springboot2 在Java項目中你們是如何配置時間格式響應給前端呢

在 Spring Boot 2 項目中配置時間格式&#xff0c;通常可以通過配置文件&#xff08;application.properties 或 application.yml&#xff09;或者通過 Java 代碼進行配置。以下是兩種常見的配置方式&#xff1a; 1. 通過配置文件配置時間格式&#xff1a; 在 application.pr…

mybaties plus插入數據,自動回顯 機制

結論&#xff1a;mybaties plus會將庫里數據自動回顯到 要插入的數據上 測試表格 SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- 表結構 DROP TABLE IF EXISTS t_stu; CREATE TABLE t_stu (id int NOT NULL COMMENT id,name varchar(255) CHARACTER SET utf8mb4 COLLATE…

【PyTorch】計算設備

文章目錄 1. 介紹2. 查詢和使用 1. 介紹 CPU設備意味著所有物理CPU和內存&#xff0c; 這意味著PyTorch的計算將嘗試使用所有CPU核心。可以用以下方式表示&#xff1a; torch.device(cpu) GPU設備只代表一個GPU和相應的顯存。 torch.device(cuda)如果有多個GPU&#xff0c;我們…

Java解決矩陣對角線元素的和問題

Java解決矩陣對角線元素的和問題 01 題目 給你一個正方形矩陣 mat&#xff0c;請你返回矩陣對角線元素的和。 請你返回在矩陣主對角線上的元素和副對角線上且不在主對角線上元素的和。 示例 1&#xff1a; 輸入&#xff1a;mat [[1,2,3],[4,5,6],[7,8,9]] 輸出&#xff1a…

為什么流量對店鋪轉化率重要?亞馬遜、速賣通等跨境賣家通過自養號測評提升店鋪轉化率

亞馬遜、速賣通等電商平臺賣家非常清楚流量對店鋪轉化率的重要性&#xff0c;測評補單在跨境電商賣家中扮演著重要的角色&#xff0c;是一種必要的運營手段之一。在追求更好的產品曝光和更高的轉化率時&#xff0c;Listing的排名是關鍵因素之一。而在各個平臺的Listing中&#…

正確使用AFX_MANAGE_STATE宏管理MFC模塊狀態, AFX_MANAGE_STATE宏作用,真的很重要!!!

簡介&#xff1a; 在使用 MFC&#xff08;Microsoft Foundation Classes&#xff09;開發 DLL&#xff08;動態鏈接庫&#xff09;時&#xff0c;正確管理 MFC 模塊狀態是確保功能正常運行的關鍵。本文將深入探討使用 AFX_MANAGE_STATE 宏的重要性&#xff0c;以及在 DLL 中正確…

連接Redis報錯解決方案

連接Redis報錯&解決方案 問題描述&#xff1a;Could not connect to Redis at 127.0.0.1:6379: 由于目標計算機積極拒絕&#xff0c;無法連接。 問題原因&#xff1a;redis啟動方式不正確 解決方案&#xff1a; 在redis根目錄下打開命令行窗口&#xff0c;輸入命令redi…

聽GPT 講Rust源代碼--src/tools(12)

File: rust/src/tools/rust-analyzer/crates/rust-analyzer/src/config.rs 在Rust源代碼中&#xff0c;rust/src/tools/rust-analyzer/crates/rust-analyzer/src/config.rs文件的作用是定義和解析rust-analyzer的配置文件。該文件包含了各種配置項的數據結構和枚舉類型&#xf…

MQTT主題、通配符和最佳實踐

MQTT主題在MQTT生態系統非常重要&#xff0c;因為代理&#xff08;broker&#xff09;依賴主題確定哪個客戶端接收指定的主題。本文我們將聚集MQTT主題、MQTT通配符&#xff0c;詳細討論使用它們的最佳實踐&#xff0c;也會探究SYS主題&#xff0c;提供給代理&#xff08;broke…

【npm | npm常用命令及鏡像設置】

npm常用命令及鏡像設置 概述常用命令對比本地安裝全局安裝--save &#xff08;或 -S&#xff09;--save-dev &#xff08;或 -D&#xff09; 鏡像設置設置鏡像方法切換回npm官方鏡像選擇鏡像源 主頁傳送門&#xff1a;&#x1f4c0; 傳送 概述 npm致力于讓 JavaScript 開發變得…

iOS——UIPickerView選擇器

UIPickerView UIPickerView是 iOS 開發中常用的用戶界面組件之一&#xff0c;用于在垂直方向上顯示一個滾動的列表&#xff0c;用戶可以通過滾動選擇其中的一項。 UIPickerView的協議方法 UIPickerView和UItableView差不多&#xff0c;UIPickerView也要設置代理和數據源。UI…

fl studio2024試用版本如何漢化中文?

fl studio2024全稱Fruity Loops Studio2024&#xff0c;這款軟件也被人們親切的稱之為水果&#xff0c;它是一款功能強大的音樂創作編輯軟件&#xff0c;擁有全功能的錄音室&#xff0c;大混音盤以及先進的音樂制作工具&#xff0c;用戶通過使用該軟件&#xff0c;就可以輕松制…

git上傳流程

git安裝網址&#xff1a;https://git-scm.com 如果您要將本地文件夾上傳到名為"compiling"的GitHub倉庫&#xff0c;可以按照以下步驟進行操作&#xff1a; 1.安裝無腦下一步 2.cd到想上傳的文件夾的上一級目錄 2.初始化Git倉庫&#xff1a;git init 設置分支&a…

C++特殊類設計

1.設計不能被拷貝的類 解析&#xff1a;拷貝只會放生在兩個場景中 拷貝構造函數賦值運算符重載 因此想要讓一個類禁止拷貝&#xff0c; 就需讓該類不能調用“拷貝構造函數”以及“賦值運算符重載”&#xff0c;而C11提供的delete重載關鍵字可以讓這件事情變得更加簡單。 1.1.C9…

stl庫之list鏈表與例題

stl中的list是雙向鏈表&#xff0c;優點在于插入/刪除元素方便&#xff0c;缺點是隨機訪問元素時間長 所需頭文件&#xff1a;#include <list> 初始化 list<類型名> 變量名 定義一個int類型的變量a list<int> a; 在末尾插入元素 a.push_back(i); 在開…

LeetCode 每日一題 Day 8 || 簡單枚舉

2048. 下一個更大的數值平衡數 如果整數 x 滿足&#xff1a;對于每個數位 d &#xff0c;這個數位 恰好 在 x 中出現 d 次。那么整數 x 就是一個 數值平衡數 。 給你一個整數 n &#xff0c;請你返回 嚴格大于 n 的 最小數值平衡數 。 示例 1&#xff1a; 輸入&#xff1a;n …

Error: Cannot find module ‘@npmcli/config‘ 最新解決辦法

看了網上許多這個問題的小伙伴&#xff0c;都是降級node版本來解決的。但是降級并不是我想要的結果。 真正的解決辦法就是更新nvm&#xff0c;將你的nvm升級到最新版本&#xff0c;然后卸載掉npm報錯的node版本&#xff0c;重新安裝即可使用。 解決辦法&#xff1a;更新nvm nv…