Divide and Conquer istifadə edərək maksimum subarray cəmi

Problem bəyanat

“Divide and Conquer istifadə edərək maksimum subarray cəmi” problemində bir array həm müsbət, həm də mənfi tam ədədi. Bitişik alt dizinin ən böyük cəmini tapacaq bir proqram yazın.

Giriş Formatı

Bir tam ədədi olan ilk sətir.

N tam ədədi ehtiva edən bir sıra ədədi olan ikinci sətir.

Çıxış formatı

Verilən massivin maksimum cəm ​​subarrayını ifadə edən tam ədədi çap edin.

Məhdudiyyətlər

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

misal

5
-10 2 5 12 -5

19

Alqoritm

Burada istifadə edirik Bölün və fəth edin yanaşma. Maksimum subarray cəmini O (nLogn) vaxtında tapa bilərik. Divide and Conquer alqoritmi aşağıdakılardır.

1. Dizini iki hissəyə bölün.

2. Sol subarray üçün maksimum subarray cəmini təkrarən tapın.

3. Doğru subarray üçün maksimum subarray cəmini təkrarən tapın.

4. Orta nöqtəni keçən maksimal subarray cəmini tapın.

5. Yuxarıdakı üç cəmin maksimumunu qaytarın.

2 və 3 sətirlər sadə rekursiv zənglərdir. Subarray orta nöqtəni keçməsi üçün maksimum subray cəmini necə tapmaq olar? Xətti vaxtda kəsişmə cəmini asanlıqla tapa bilərik. Fikir sadədir, orta nöqtədən başlayaraq ortanın solundakı bir nöqtədə bitən maksimum cəmi tapın, sonra orta + 1 ortasından başlayaraq + ortanın sağındakı cəm nöqtəsi ilə bitən maksimum cəmi tapın. Nəhayət iki və qayıt.

Həyata keçirilməsi

Divide and Conquer istifadə edərək maksimum subarray cəmi üçün C ++ proqramı

#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;
}

Divide and Conquer istifadə edərək maksimum subarray cəmi üçün Java proqramı

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

Divide and Conquer istifadə edərək maksimum subarray cəmi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * logn) hara n verilmiş massivin ölçüsüdür. Budur, bu təkrarlanma əlaqəsi ilə gəlirik t (n) = 2 * t (n / 2) + θ (n). Bu təkrarlanma münasibətini həll etdikdə t (n) dəyərini n * logn olaraq əldə edin.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.