สมมติว่าเรามีเมทริกซ์ 2 มิติ เราต้องหาเมทริกซ์ย่อย k × k ที่ใหญ่ที่สุด โดยที่องค์ประกอบทั้งหมดมีค่าเท่ากัน จากนั้นจึงหาค่าของ k
ดังนั้นหากอินพุตเป็นแบบ
| 1 | 1 | 8 | 3 |
| 1 | 5 | 5 | 5 |
| 2 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากมีเมทริกซ์กำลังสอง 3 × 3 ของค่า 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=จำนวนแถวของเมทริกซ์
-
m :=จำนวนคอลัมน์ของเมทริกซ์
-
กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n x m) และเติมด้วย 1
-
ยกเลิก :=1
-
สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -
-
สำหรับการเริ่มต้น j :=m - 1 เมื่อ j>=0, อัปเดต (ลด j โดย 1) ให้ทำ -
-
val :=inf
-
ถ้า i + 1
-
val :=ต่ำสุดของ dp[i + 1, j] และ val
-
-
มิฉะนั้น
-
ค่า :=0
-
-
ถ้า j + 1
-
val :=ค่าต่ำสุดของ dp[i, j + 1] และ val
-
-
มิฉะนั้น
-
ค่า :=0
-
-
ถ้า i + 1
-
val :=ต่ำสุดของ dp[i + 1, j + 1] และ val
-
-
มิฉะนั้น
-
ค่า :=0
-
-
ถ้า val เหมือนกับ inf แล้ว −
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
dp[i, j] :=dp[i, j] + วาล
-
ret :=สูงสุดของ ret และ dp[i, j]
-
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& v) {
int n = v.size();
int m = v[0].size();
vector<vector<int>> dp(n, vector<int>(m, 1));
int ret = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int val = INT_MAX;
if (i + 1 < n && v[i + 1][j] == v[i][j]) {
val = min(dp[i + 1][j], val);
}
else {
val = 0;
}
if (j + 1 < m && v[i][j + 1] == v[i][j]) {
val = min(dp[i][j + 1], val);
}
else {
val = 0;
}
if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
val = min(dp[i + 1][j + 1], val);
}
else {
val = 0;
}
if (val == INT_MAX)
continue;
dp[i][j] += val;
ret = max(ret, dp[i][j]);
}
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
int main(){
vector<vector<int>> matrix = {
{1, 1, 8, 3},
{1, 5, 5, 5},
{2, 5, 5, 5},
{4, 5, 5, 5}
};
cout << solve(matrix);
} อินพุต
{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} }; ผลลัพธ์
3
