סכום המשך מרבי כזה שלא יהיו שלושה רצופים


רמת קושי בינוני
נשאל לעתים קרובות מעבדות חדשנות 24 * 7 אקסנצ'ר אמזון בעברית מסירה פייפאל PayU
מערך תכנות דינמי

הבעיה "סכום המשך מקסימלי כזה שלא יהיו שלוש רצופות" קובעת שאתה מקבל מערך of מספרים שלמים. כעת עליך למצוא המשך בעל הסכום המקסימלי בהינתן שאתה לא יכול להתחשב בשלושה אלמנטים עוקבים. כזכור, המשך אינו אלא מערך שנותר כאשר חלק מהאלמנטים מוסרים ממערך הקלט המקורי ושומרים על הסדר זהה.

דוגמה

סכום המשך מרבי כזה שלא יהיו שלושה רצופים

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

הסבר

זו הייתה בחירה קלה לבחור 5 ו- 10. מכיוון שכל דרך אחרת לא תביא לסכום גדול יותר.

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

הסבר

אנחנו לא בוחרים את 5 שנמצאים באמצע המערך. מכיוון שהדבר ייצור המשך שאינו מקיים את התנאי המוטל בשאלה.

גישה

הבעיה ביקשה מאיתנו למצוא את ההמשך עם סכום מרבי כך שלא נבחרים שלושה אלמנטים עוקבים. לפיכך גישה נאיבית יכולה להיות דור ההמשך. כפי שעשינו בכמה מהשאלות הקודמות. הגישה הנאיבית היא לרוב, לייצר את ההשלכות ואז לבדוק אם ההמשך עונה על התנאים המוטלים בשאלה. אך גישה זו גוזלת זמן ולא ניתן להשתמש בה באופן מעשי. מכיוון שהשימוש בגישה אפילו לתשומות בגודל בינוני יעלה על מגבלות הזמן. לכן כדי לפתור את הבעיה עלינו להשתמש בשיטה אחרת.

אנחנו נשתמש תכנות דינמי כדי לפתור את הבעיה, אך לפני כן, עלינו לבצע מעט עבודות תיקים. עבודת מקרה זו נעשית כדי להפחית את הבעיה הראשונית לבעיות משנה קטנות יותר. מכיוון שבתכנות דינמי, אנו מצמצמים את הבעיה לבעיות משנה קטנות יותר. לכן, שקול שאנחנו מדלגים על האלמנט הנוכחי ואז הבעיה שלנו מצטמצמת לפתרון הבעיה עד האלמנט הקודם. שקול, אנחנו כן בוחרים את האלמנט הנוכחי. ואז יש לנו שתי אפשרויות עבור האלמנט הקודם. או שנבחר את האלמנט הקודם, אם כן אז לא נוכל לבחור את האלמנט הקודם לאלמנט הקודם. אך אם לא, הבעיה מצטמצמת לפתור את הבעיה עד לפני האלמנט הקודם. יהיה קל יותר להבין באמצעות הקוד.

קופונים

קוד 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

ניתוח מורכבות

מורכבות זמן

O (N) כי פשוט עברנו את המערך והמשכנו למלא את מערך ה DP שלנו. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (N) כי היינו צריכים ליצור מערך DP חד מימדי לאחסון הערכים. מורכבות החלל היא גם לינארית.