ค้นหาเมทริกซ์ย่อยสี่เหลี่ยมพื้นที่ที่ใหญ่ที่สุดซึ่งมีผลรวมเท่ากับ k ใน C++

สมมติว่าเรามีเมทริกซ์เมทริกซ์ 2 มิติและค่า K เราต้องหาเมทริกซ์ย่อยรูปสี่เหลี่ยมผืนผ้าที่ยาวที่สุดซึ่งผลรวมเท่ากับ K

ดังนั้นหากอินพุตเป็นแบบ

และ K =9

จากนั้นผลลัพธ์จะเป็นจุดบนซ้ายคือ (1, 0) และจุดล่างขวาคือ (3, 2)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• MAX :=100

• กำหนดฟังก์ชัน sum_k() ซึ่งจะใช้เวลาหนึ่งอาร์เรย์ arr, start, end, n, k,

• กำหนดหนึ่งแผนที่

• ผลรวม :=0, maximum_length :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • sum :=sum + arr[i]

  • ถ้าผลรวมเท่ากับ k แล้ว −

    • ความยาวสูงสุด :=ผม + 1

    • เริ่ม :=0

    • จบ :=ผม

  • หากผลรวมไม่อยู่ในแผนที่ −

    • map[sum] :=i

  • ถ้า (ผลรวม - k) อยู่ในแผนที่ −

    • ถ้า maximum_length <(i - map[sum - k]) แล้ว −

      • ความยาวสูงสุด :=i - map[sum - k]

      • start :=map[sum - k] + 1

      • จบ :=ผม

• คืนค่า true เมื่อ maximum_length ไม่ใช่ 0

• จากวิธีหลัก ให้ทำดังนี้ −

• row :=จำนวนแถวของ mat, col :=จำนวนคอลัมน์ของ mat

• กำหนดอุณหภูมิอาร์เรย์ของขนาด:แถว

• กำหนดอาร์เรย์ final_point ={0,0,0,0}

• maxArea :=-inf

• สำหรับการเริ่มต้น left :=0 เมื่อซ้าย

  • เติมอุณหภูมิด้วย 0

  • สำหรับการเริ่มต้น right :=left, when right

    • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <แถว อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

      • temp[i] :=temp[i] + mat[i, right]

    • sum :=sum_k(ชั่วคราว ขึ้น ลง แถว k)

    • พื้นที่ :=(ลง - ขึ้น + 1) * (ขวา - ซ้าย + 1)

    • ถ้าผลรวมไม่เป็นศูนย์และ maxArea <พื้นที่แล้ว −

      • final_point[0] :=ขึ้น, final_point[1] :=ลง

      • final_point[2] :=ซ้าย final_point[3] :=ขวา

      • maxArea :=พื้นที่

  • ถ้า final_point คือ [0,0,0,0] และ mat[0,0] ไม่ใช่ k ดังนั้น

    • ส่งคืน "ไม่พบเมทริกซ์ย่อย"

• แสดงจุดซ้ายบน (final_point[0], final_point[2])

• แสดงจุดล่างขวา (final_point[1], final_point[3])

• แสดงองค์ประกอบเสื่อ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;const int MAX =100;bool sum_k (int arr[], int&start, int&end, int n, int k) { แผนที่ unordered_map; int sum =0, maximum_length =0; สำหรับ (int i =0; i > &mat, int k) { int row =mat.size(); int col =mat[0].size(); int temp[แถว] พื้นที่; ผลรวมบูล; int ขึ้น, ลง; เวกเตอร์ final_point ={0,0,0,0}; int maxArea =INT_MIN; สำหรับ (int ซ้าย =0; ซ้าย > v ={ { 2, 8, -5, 6 }, { -7, 7, 8, -3 }, { 11, -14, 4, 3 }, { -4, 3, 1, 10 }}; sum_zero(v, 9);}

อินพุต

ผลลัพธ์

(บน, ซ้าย) พิกัด:(1, 0)(ล่าง, ขวา) พิกัด:(3, 2)-7 7 811 -14 4-4 3 1