סכום מקסימלי של תת-מערך באמצעות חלוקה וכיבוש  


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

הצהרת בעיה  

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

פורמט הכנסה  

השורה הראשונה המכילה מספר שלם N.

שורה שנייה המכילה מערך של מספרים שלמים המכילים מספרים שלמים N.

פורמט פלט  

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

אילוצים  

  • 1 <= N <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 5

דוגמה  

5
-10 2 5 12 -5
19

אַלגוֹרִיתְם  

כאן אנו משתמשים הפרד ומשול גִישָׁה. אנו יכולים למצוא את הסכום המקסימלי של מערך המשנה בזמן O (nLogn). להלן האלגוריתם Divide and Conquer.

1. חלק את המערך לשני חלקים.

2. מצא באופן רקורסיבי את הסכום המקסימלי של תת-המערך עבור מערך המשנה השמאלי.

3. מצא באופן רקורסיבי את הסכום המקסימלי למערך המשנה הנכון.

4. מצא את הסכום המרבי של תת-המערך החוצה את נקודת האמצע.

5. החזר את המקסימום של שלושת הסכומים הנ"ל.

שורות 2 ו -3 הן שיחות רקורסיביות פשוטות. כיצד למצוא את סכום תת-המערך המקסימלי כך שמתחת המשנה חוצה את נקודת האמצע? אנו יכולים למצוא את סכום המעבר בקלות בזמן ליניארי. הרעיון הוא פשוט, מצא את הסכום המקסימלי החל מנקודת האמצע וכלה בנקודה כלשהי משמאל לאמצע, ואז מצא את הסכום המקסימלי החל מאמצע + 1 וכלה בנקודת סכום בצד ימין של אמצע + 1. לבסוף, שלב את שניים וחוזרים.

ראה גם
ניתן מערך זוגות מצא את כל הזוגות הסימטריים בו

יישום  

תכנית C ++ לסכום מקסימלי של תת-מערך באמצעות חלוקה וכיבוש

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

int cross_sum(int arr[], int l, int m, int h)
{
  int sum = 0;
  int left_sum = INT_MIN;
  for (int i = m; i >= l; i--) 
  {
    sum = sum + arr[i];
    if (sum > left_sum)
      left_sum = sum;
  }
  sum = 0;
  int right_sum = INT_MIN;
  for (int i = m + 1; i <= h; i++) 
  {
    sum = sum + arr[i];
    if (sum > right_sum)
      right_sum = sum;
  }
  return max(left_sum + right_sum, max(left_sum, right_sum));
}


int max_sum(int arr[], int l, int h)
{
  if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return max(max_sum(arr, l, m), max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
} 

int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int sum = max_sum(a,0,n-1);
  cout<<sum<<endl;
  return 0;
}

תוכנית Java לסכום מקסימלי של תת-מערך באמצעות חלוקה וכיבוש

import java.util.Scanner;
class sum
{
    public static int cross_sum(int arr[], int l, int m, int h)
    {
            int sum = 0;
            int left_sum = -1000000;
            for (int i = m; i >= l; i--) 
            {
                    sum = sum + arr[i];
                    if (sum > left_sum)
                            left_sum = sum;
            }
            sum = 0;
            int right_sum = -1000000;
            for (int i = m + 1; i <= h; i++) 
            {
                    sum = sum + arr[i];
                    if (sum > right_sum)
                            right_sum = sum;
            }
            return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum));
    }
    public static int max_sum(int arr[], int l, int h) 
    {
        if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return Math.max(max_sum(arr, l, m), Math.max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum = max_sum(a,0,n-1);
        System.out.println(sum);
    }
}
7
10 5 -106 29 100 1000 -500
1129

ניתוח מורכבות לסכום מקסימלי של תת-מערך באמצעות חלוקה וכיבוש  

מורכבות זמן

O (n * logn) איפה n הוא גודל המערך הנתון. כאן אנו באים עם יחס הישנות זה t (n) = 2 * t (n / 2) + θ (n). כאשר אנו פותרים את יחס ההישנות הזה נקבל את הערך של t (n) כ- n * logn.

ראה גם
עומק מינימלי של פתרון Leetcode עץ בינארי

מורכבות בחלל

O (1) כי איננו משתמשים בשום שטח עזר כאן.