סכום מקסימלי של הגדלת המשך  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ Atlassian בלומברג Byte Citrix CodeNation קופנג eBay פייסבוק Google יבמ מיקרוסופט נגארו אורקל סופר יאהו
מערך חיפוש בינארי תכנות דינמי

הצהרת בעיה  

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

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

דוגמה  

4
18 5 17 23
45

הסבר: בדוגמה שלעיל, 45 הוא הסכום המקסימלי. בדוגמה שלעיל, יש שתי המשך הגדלה כלומר, {18, 17} ו- {5, 17, 23}. אבל בהמשך השני יש את הסכום המקסימלי.

גישה  

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

דוגמא-  [2,5,8,3,4,6]

ואז כמה המשכים הולכים וגדלים הם - 

[2,5,8], סכום = 15

[2,8], סכום = 10

[5,8], סכום = 13

[2,3,4,6], סכום = 15

[2,5,6], סכום = 13 וכו ' הסכום המקסימלי שנקבל הוא 15.

ניתן לפרק את הבעיה לבעיות משנה פשוטות, כלומר יש לה תשתית אופטימלית. וגם לבעיה יש בעיות משנה חופפות אם נצייר את עץ הרקורסיה שלו. מכיוון שלבעיה יש מבנה אופטימלי ותתי בעיות חופפות, ניתן לפתור את הבעיה באמצעות תכנות דינמי. תן ל- [0,1, …… n-1] להיות מערך ו- dp [i] = סכום מקסימלי של הגדלת המשך המסתיים באינדקס i, כך ש- [i] הוא האלמנט האחרון.

ואז ניתן לכתוב dp [i] כ, 

dp [i] = a [i] + מקסימום (L [j]) כאשר 0

ה- ans יהיו מקסימום (dp [i]) כאשר 0

גישה  

  1. ניצור מערך חדש dp, כאשר dp [i] = a [i], שבו 0
  2. נפעיל לולאה חיצונית מ- 0 <i <n.
  3. לכל i המאחסן סכום מקסימלי של הגדלת המשך של [0, i-1] שמסתיים ב- i. מצא את הגדלת המשך עם הסכום המרבי שמסתיים ב- [j], כאשר [j] קטן מהיסוד הנוכחי a [i]
  4. מצא את המקסימום במערך dp.

יישום  

תכנית C ++ להמשך הגדלת הסכום המרבי

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

int max_sum_inc_sub(vector<int> a,int n){
  vector<int> dp(a);
  int ans = 0;
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
        dp[i] = dp[j]+a[i];
      }
    }
    ans = max(ans,dp[i]);
  }
  return ans;
}
int main() {
  int n;
  cin>>n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    a.push_back(x);
  }
  int max_sum = max_sum_inc_sub(a,n);
  cout<<max_sum<<endl;
  return 0;
}

תכנית Java להמשך הגדלת סכום מרבי

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_sum_inc_sub(arr,n);
        System.out.println(ans);
  }
  
  public static int max_sum_inc_sub(int[] a,int n){
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
        	dp[i]=a[i];
        }
        int ans = 0;
    for(int i=1;i<n;i++){
      for(int j=0;j<i;j++){
        if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
          dp[i] = dp[j]+a[i];
        }
      }
      ans = Math.max(ans,dp[i]);
    }
    return ans;
    }

}
6
2 5 8 3 4 6
15

ניתוח מורכבות לסכום מרבי של הגדלת ההמשך  

מורכבות זמן

O (n * n) איפה n הוא גודל המערך הנתון. כאן אנו מפעילים שניים מקוננים לולאות מה שמוביל אותנו למורכבות זמן ריבועית.

ראה גם
סכום זוגות מרבי עם הבדל ספציפי

מורכבות בחלל

O (n) כי אנו משתמשים במערך 1-D. כאן אנו שומרים ערכים במערך dp ליניארי.