ผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะ  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ Coursera เดลี โฟร์ไคต์ Snapdeal
แถว การเขียนโปรแกรมแบบไดนามิก

ปัญหา "ผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะ" ระบุว่าคุณได้รับอาร์เรย์ของ จำนวนเต็ม และจำนวนเต็ม K. จากนั้นเราจะขอให้หาผลรวมสูงสุดของคู่อิสระ เราสามารถจับคู่จำนวนเต็มสองจำนวนได้หากพวกมันมีผลต่างสัมบูรณ์น้อยกว่า K ดังนั้นเราจำเป็นต้องหาผลรวมสูงสุดของคู่ x ที่เป็นจำนวน 2x

ตัวอย่าง  

ผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะหมุด

42, 43, 4, 5, 6, 12
96

คำอธิบาย

เราเลือก 42, 43 และ 5, 6 เรามีตัวเลือกระหว่าง 4, 5 และ 6 ดังนั้นเราจึงหาค่าสูงสุดในหมู่พวกมันทำให้ผลลัพธ์ = 96

เข้าใกล้  

ปัญหาขอให้เราหาผลรวมสูงสุดที่สามารถทำได้หากเราจับคู่องค์ประกอบบางอย่างของ แถว. เราสามารถจับคู่องค์ประกอบภายใต้เงื่อนไขที่กำหนดว่าองค์ประกอบควรมีความแตกต่างสัมบูรณ์น้อยกว่า K ก่อนที่จะแก้ปัญหาเรา ประเภท อาร์เรย์ ด้วยวิธีนี้เรากำลังตัดพื้นที่การค้นหาของเรา พิจารณาว่าเรามีอาร์เรย์ที่ไม่ได้เรียงลำดับ จากนั้นเราจะต้องสำรวจองค์ประกอบทั้งหมดเพื่อจับคู่องค์ประกอบ แต่หลังจากจัดเรียงแล้วเรารู้ว่าองค์ประกอบที่ใหญ่ที่สุดเป็นเพียงองค์ประกอบที่อยู่ก่อนหน้านั้น ดังนั้นเราจึงตรวจสอบว่าเงื่อนไขเป็นที่พอใจหรือไม่

ดูสิ่งนี้ด้วย
สี่เหลี่ยมผืนผ้าผลรวมสูงสุดในเมทริกซ์ 2 มิติ

หากเงื่อนไขเป็นที่พอใจเราจะจับคู่องค์ประกอบก่อนหน้าและปัจจุบันและเพิ่มผลลัพธ์สำหรับปัญหาจนถึงองค์ประกอบที่สองสุดท้าย (จากองค์ประกอบปัจจุบัน) แต่ถ้าไม่พอใจสภาพ. เราออกจากการจับคู่และผลลัพธ์จะเหมือนกับของจนถึงองค์ประกอบก่อนหน้า อย่างเป็นทางการผลลัพธ์ [i] = ผลลัพธ์ [i-2] + อินพุต [i] + อินพุต [i-2] หากการจับคู่เสร็จสิ้นมิฉะนั้นผลลัพธ์ [i] = ผลลัพธ์ [i-1] นี่คืออาร์เรย์ผลลัพธ์ของเรา DP อาร์เรย์เนื่องจากเรากำลังจัดเก็บผลลัพธ์ของปัญหาย่อยที่เล็กกว่า เรารวมผลลัพธ์ของปัญหาย่อยที่มีขนาดเล็กเหล่านี้เพื่อค้นหาผลลัพธ์ของปัญหาดั้งเดิมเช่นเดียวกับที่เราทำใน DP จากล่างขึ้นบน

รหัส  

รหัส C ++ เพื่อค้นหาผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะ

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

รหัส Java เพื่อค้นหาผลรวมสูงสุดของคู่ที่มีความแตกต่างเฉพาะ

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา 

O (NlogN) นี่เป็นเพราะเราได้จัดเรียงอาร์เรย์ในตอนแรก และผสานการเรียงลำดับและอัลกอริทึมการเรียงลำดับอื่น ๆ สามารถจัดเรียงอาร์เรย์ใน O (NlogN) หากเราได้รับข้อมูลที่จัดเรียงไว้เราสามารถแก้ไขปัญหาได้ในเวลา O (N)

ดูสิ่งนี้ด้วย
เมทริกซ์ย่อยรูปสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดซึ่งมีผลรวมเป็น 0

ความซับซ้อนของอวกาศ

บน), พื้นที่นี้จำเป็นสำหรับการจัดเรียงอาร์เรย์ แม้ว่าเราจะไม่ได้สร้างอาร์เรย์ DP และจะใช้อาร์เรย์อินพุตเดียวกันสำหรับตาราง DP โซลูชันนั้นยังคงมีความซับซ้อนของพื้นที่เท่าเดิมเนื่องจากต้องใช้ช่องว่างนี้ในการเรียงลำดับ