ተደራራቢ ንዑስ-ድርደራዎች K ከፍተኛ ድምር


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ የኮድ ቁጥር ዴል ፌስቡክ GE የጤና google Qualcomm
ሰልፍ ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ

“K ተደራራቢ ንዑስ-ድርድሮች ከፍተኛው ድምር” ችግሩ ብዙ ቁጥር እንደሚሰጥዎት ይገልጻል ፡፡ የእነሱ ድምር ከፍተኛ ስለሆነ ከፍተኛውን የ k-subarrays ድምር ይፈልጉ። እነዚህ የኪ-ንዑስ መርከቦች ተደራራቢ ሊሆኑ ይችላሉ ፡፡ ስለዚህ ፣ ድምር ከሌሎቹ ንዑስ አንቀሳቃሾች መካከል ከፍተኛው ስለሆነ የ k-subarrays ን መፈለግ አለብን ፡፡

ለምሳሌ

ተደራራቢ ንዑስ-ድርደራዎች K ከፍተኛ ድምር

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

ማብራሪያ-ንዑስ ክፍል ድምር = 50 ያለው ከፍተኛ ዋጋ አለው ፡፡ ከዚያ በኋላ እኛ በግራ ወይም በቀኝ አቅጣጫ ድምር ከቀነሰን ፡፡ ስለዚህ ፣ ወደ ግራ አቅጣጫ የምንንቀሳቀስ ከሆነ ፡፡ -50 እና 10 እርስ በእርሳቸው ስለሚሰረዙ እንደገና 10 ድምርን ማግኘት እንችላለን ፡፡ ግን በትክክለኛው አቅጣጫ የምንጓዝ ከሆነ ድምርታችን እየቀነሰ የሚሄድ ብቻ ነው የሚሆነው ፡፡ ስለዚህ እኛ ልናገኘው የምንችለው ከሁሉ የተሻለው መልስ ይህ ነው ፡፡

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

ማብራሪያ-እዚህ ከሁለቱ ቁጥሮች አንዱን ካዋሃድን ያ የከፋ መፍትሄ ያስከትላል ፡፡ ስለዚህ አንድ ነጠላ ቁጥር መምረጥ የተሻለ ይሆናል። ስለሆነም ነጠላ ቁጥሮችን እንመርጣለን -1 -2 -3. ሌላ ማንኛውም ጥምረት የከፋ ውጤት ይሰጠናል።

ተደራራቢ ንዑስ-ድርድሮች ለ K ከፍተኛ ድምርዎች አቀራረብ

ችግሩ በሁሉም ንዑስ ቡድን ውስጥ ካሉ ሁሉም ድምርዎች መካከል የከፍተኛው ድምርን እንድናገኝ ይጠይቀናል ፡፡ ስለዚህ ፣ ለመጠቀም ካሰብን የካዳኔስ ስልተ ቀመር ችግሩን መፍታት አንችልም ፡፡ ምክንያቱም የካዳኔ ስልተ ቀመር ከፍተኛውን ድምር ለማግኘት ሊያገለግል ይችላል። ግን ያ ሁለተኛውን ከፍተኛውን ፣ ሦስተኛውን ከፍተኛውን እና ሌሎችን ማግኘት አይችልም ፡፡ የካዳኔ ስልተ-ቀመር በዋነኝነት የሚያተኩረው የመጀመሪያውን ከፍተኛውን ለማግኘት ሲሆን የሚቀጥለውን ከፍተኛ ንዑስ ቡድን ድምርን ለማግኘት አይደለም ፡፡ እዚህ የ ‹ዝቅተኛ KSum› እና ‹ከፍተኛ› KSum ሁለት ድርድሮችን እንፈጥራለን ፡፡ አሁን ላለው መረጃ ጠቋሚ የ ‹ንዑስ› ድምርን ለማግኘት ቅድመ ቅጥያ ድምር ድርድርን እንጠቀማለን ፡፡ የድርድር አነስተኛ KSum ዝቅተኛውን አነስተኛ ንዑስ መርሃግብሮችን ይይዛል። ድርድር ቢበዛ KSum ከፍተኛውን የኪራይ ማከፋፈያ ድምር ይይዛል። አሁን ለእያንዳንዱ መረጃ ጠቋሚ አነስተኛውን የ ‹KSum› እና ከፍተኛውን ‹KSum ›ድርድርን እናዘምነዋለን ፡፡ በድርድሩ ውስጥ ካለፉ በኋላ መልስ በከፍተኛው KSum ውስጥ ይቀመጣል።

ኮድ

ተደራራቢ ንዑስ ድርድር K ከፍተኛ ድምርን ለማግኘት የ C ++ ኮድ

#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

ተደራራቢ ንዑስ-ድርብ ከፍተኛውን ድምር ኬ ለማግኘት የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት ኦ (k * N)

በትንሹ KSum ውስጥ ማስገባት እና በከፍተኛው የ KSum ውስጥ ማስገባት O (k) ጊዜ ይወስዳል። እናም ይህንን ሂደት በእያንዳንዱ የድርድር አካል ላይ በሚሽከረከረው ሉፕ ውስጥ እንሰራለን ፡፡ ስለሆነም አጠቃላይ የጊዜ ውስብስብነቱ ነው ኦ (k * n).

የቦታ ውስብስብነትኦ (ኤን)

ለቦታ የላይኛው ወሰን ምልክት በሆነው በግብዓት አርራይ ውስጥ ግቤቱን እያከማቸነው ነው ፡፡ ስለዚህ የመፍትሔው የቦታ ውስብስብነት መስመራዊ ነው።