ผลรวมสูงสุดในลำดับต่อมาที่ไม่มีสามตัวติดต่อกัน  


ระดับความยาก กลาง
ถามบ่อยใน ห้องทดลองนวัตกรรม 24 * 7 แอคเซนเจอร์ อเมซอน เดลี บัตรเครดิต/เดบิต หรือ PayPal payu
แถว การเขียนโปรแกรมแบบไดนามิก

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

ตัวอย่าง  

ผลรวมสูงสุดในลำดับต่อมาที่ไม่มีสามตัวติดต่อกันหมุด

a[] = {2, 5, 10}
50

คำอธิบาย

นี่เป็นทางเลือกที่ง่ายในการเลือก 5 และ 10 เนื่องจากวิธีอื่นใดจะไม่ส่งผลให้ได้ผลรวมที่มากขึ้น

a[] = {5, 10, 5, 10, 15}
40

คำอธิบาย

เราไม่เลือก 5 ที่อยู่ตรงกลางของอาร์เรย์ เพราะนั่นจะเป็นการสร้างความต่อเนื่องที่ไม่เป็นไปตามเงื่อนไขที่กำหนดไว้ในคำถาม

เข้าใกล้  

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

ดูสิ่งนี้ด้วย
นับลำดับไบนารีที่มีความยาวเท่ากันโดยมีผลรวมของบิตครึ่งแรกและครึ่งหลังเท่ากัน

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

รหัส  

รหัส C ++ เพื่อค้นหาผลรวมสูงสุดในลำดับต่อมาที่ไม่มีสามตัวติดต่อกัน

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

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    int dp[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
    cout<<dp[n-1];
}
16

รหัส Java เพื่อค้นหาผลรวมลำดับสูงสุดที่ไม่มีสามตัวติดต่อกัน

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = a.length;
    int dp[] = new int[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

    System.out.println(dp[n-1]);
  }
}
16

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

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

บน), เพราะเราเพียงแค่ข้ามอาร์เรย์และเติมอาร์เรย์ DP ของเราต่อไป ดังนั้นความซับซ้อนของเวลาจึงเป็นเชิงเส้น

ดูสิ่งนี้ด้วย
อัลกอริทึม MiniMax

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

บน), เพราะเราต้องสร้างอาร์เรย์ DP มิติเดียวเพื่อเก็บค่า ความซับซ้อนของพื้นที่ยังเป็นเส้นตรง