Bitişik alt-serialların üst-üstə düşən maksimum cəmi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Kod milləti Vadi Facebook GE Healthcare google Qualcomm
Geyim Dinamik proqramlaşdırmaBaxılıb 20

Problem bəyanat

Məsələ “üst-üstə düşən bitişik alt massivlərin maksimum K cəmi” sizə bir ədəd tam ədəd verildiyini bildirir. K-subarraysın maksimum cəmini tapın ki, cəmi maksimum olsun. Bu k-subarrays üst-üstə düşə bilər. Beləliklə, k-subarizi tapmaq lazımdır ki, onların cəmi digər alt mədrlər arasında maksimum olsun.

misal

Bitişik alt-serialların üst-üstə düşən maksimum cəmiPin

arr = {10,-10,20,30,-1,-2}, k = 2
50 50

İzahat: cəmi = 50 olan subarray maksimum dəyərə malikdir. Bundan sonra, solda və ya doğru istiqamətdə cəm azalır. Beləliklə, sol istiqamətdə hərəkət etsək. Yenidən 50 toplaya bilərik, çünki -10 və 10 bir-birini ləğv edir. Ancaq düzgün istiqamətdə hərəkət etsək, cəmimiz yalnız azalmağa davam edəcəkdir. Beləliklə, bu, əldə edə biləcəyimiz ən yaxşı cavabdır.

arr = {-1,-2,-3,-4}, k = 3
-1 -2 -3

İzahat: Burada iki rəqəmdən hər hansı birini birləşdirsək, bu daha pis bir həll ilə nəticələnəcəkdir. Beləliklə, tək bir nömrə seçmək daha yaxşı olacaqdır. Beləliklə, -1 -2 -3 vahid nömrələrini seçəcəyik. Hər hansı digər birləşmə bizə daha pis bir nəticə verəcəkdir.

Bitişik alt-serialların üst-üstə düşən maksimum məbləğləri üçün yanaşma

Problem, bütün alt bölmənin bütün cəmləri arasında k maksimum cəmlərini tapmağımızı xahiş edir. Beləliklə, istifadə etməyi düşünsək Kadane's alqoritm. Problemi həll edə bilməyəcəyik. Çünki Kadane alqoritmindən maksimum cəmi tapmaq üçün istifadə etmək olar. Ancaq ikinci maksimumu, üçüncü maksimumu və digərlərini tapa bilməyəcəksiniz. Kadane'nin alqoritmi əsasən ilk maksimumun tapılmasına yönəldilir və növbəti maksimum subarray cəmini tapmağı hədəfləmir. Burada minimumKSUM və maximumKSum iki sıra yaradırıq. Mövcud indeks üçün subarrays cəmini tapmaq üçün bir prefiks cəm massivindən istifadə edəcəyik. Array minimumKSum, alt qrafiklərin minimum k cəmini saxlayır. Array maximumKSum sub-masaların k maksimum cəmini saxlayır. İndi hər bir indeks üçün minimumKSum və maximumKSum dizilərini yeniləyirik. Massivdən keçdikdən sonra cavab maximumKSum daxilində saxlanılır.

Kodu

Bitişik sub-arrayın üst-üstə düşən K maksimum məbləğini tapmaq üçün C ++ kodu

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

void kMaxSubArrays(vector<int> input, int k)
{
  int n = input.size();
  vector<int> prefixSum(n);
    prefixSum[0] = input[0];
    for(int i=1;i<n;i++)
        prefixSum[i] += prefixSum[i-1] + input[i];

  vector<int> minimumKSum(k, INT_MAX);
  minimumKSum[0] = 0;

  vector<int> maximumKSum(k, INT_MIN);
  vector<int> currentSum(k);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      if(prefixSum[i] < 0 && minimumKSum[j]==INT_MAX)
            currentSum[j]=(-prefixSum[i])-minimumKSum[j];
        else
                currentSum[j] = prefixSum[i] - minimumKSum[j];
    }
        int j = 0;
        for (int l = 0; l < k; l++) {
            if (currentSum[j] > maximumKSum[l]) {
                maximumKSum.insert(maximumKSum.begin() + l, currentSum[j]);
                maximumKSum.erase(maximumKSum.begin() + k);
                j++;
            }
        }
    for (int j = 0; j < k; j++) {
            if (prefixSum[i] < minimumKSum[j]) {
                minimumKSum.insert(minimumKSum.begin() + j, prefixSum[i]);
                minimumKSum.erase(minimumKSum.begin() + k);
                break;
            }
        }
  }

  for (int element : maximumKSum)
    cout<<element<<" ";
}

int main()
{
  int inputSize;cin>>inputSize;
  vector<int> input(inputSize);
  for(int i=0;i<inputSize;i++)cin>>input[i];
  int k;cin>>k;
  kMaxSubArrays(input, k);
}
6
10 -10 20 30 -1 -2
2
50 50

Bitişik alt array üst-üstə düşən K maksimum məbləğini tapmaq üçün Java kodu

import java.util.*;

class Main{
    
    static void kMaxSubArrays(int input[], int k)
    {
    	int n = input.length;
    	int prefixSum[] = new int[n];
        prefixSum[0] = input[0];
        for(int i=1;i<n;i++)
            prefixSum[i] += prefixSum[i-1] + input[i];
    
    	int maximumKSum[] = new int[k];
    	for(int i=0;i<k;i++)
    	    maximumKSum[i] = Integer.MIN_VALUE;
    
    	int minimumKSum[] = new int[k];
    	for(int i=0;i<k;i++)
    	    minimumKSum[i] = Integer.MAX_VALUE;
    	minimumKSum[0] = 0;
    	
    	int currentSum[] = new int[k];
    	for(int i=0;i<k;i++)
    	    currentSum[i] = 0;
    
    	for (int i=0;i<n;i++) {
    		for (int j=0;j<k;j++) {
    			if(prefixSum[i] < 0 && minimumKSum[j]==Integer.MAX_VALUE)
    		        currentSum[j]=(-prefixSum[i])-minimumKSum[j];
    		    else
                    currentSum[j] = prefixSum[i] - minimumKSum[j];
    		}
            int j = 0;
            for (int l = 0; l < k; l++) {
                if (currentSum[j] > maximumKSum[l]) {
                    maximumKSum[l] = currentSum[j];
                    for(int z = l+1;z<k;z++)
                        maximumKSum[z] = maximumKSum[z-1];
                    j++;
                }
            }
    		for (j = 0; j < k; j++) {
                if (prefixSum[i] < minimumKSum[j]) {
                    minimumKSum[j] = prefixSum[i];
                    for(int z = j+1;z<k;z++)
                        minimumKSum[z] = minimumKSum[z-1];
                    break;
                }
            }
    	}
    
    	for(int i=0;i<k;i++)
    		System.out.print(maximumKSum[i]+" ");
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int inputSize = sc.nextInt();
    	int input[] = new int[inputSize];
    	for(int i=0;i<inputSize;i++)input[i] = sc.nextInt();
    	int k = sc.nextInt();
    	kMaxSubArrays(input, k);
    }
}
6
10 -10 20 30 -1 -2
2
50 50

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (k * N)

MinimumKSum-a daxil etmə və maksimumSum-a əlavə O (k) vaxt aparır. Və biz bu prosesi massivin hər bir elementi üzərində ilmə olan bir döngə daxilində edirik. Beləliklə, ümumi zaman mürəkkəbliyi O (k * n).

Kosmik Mürəkkəblik: O (N)

Girişi boşluq üçün yuxarı həddi göstərən inputArray-da saxlayırıq. Beləliklə həllin kosmik mürəkkəbliyi xətti olur.

Translate »