ק מאַקסימום סאַמז פון אָוווערלאַפּינג קאַנטיגיואַס סאַב-ערייז


שוועריקייט לעוועל שווער
אָפט געבעטן אין קאָדנאַטיאָן דעל facebook גע העאַלטהקאַרע גוגל קוואַלקאַם
מענגע דינאַמיש פּראָגראַממינג

פּראָבלעם סטאַטעמענט

די פּראָבלעם "ק מאַקסימום סאַמז פון אָוווערלאַפּינג קאַנטיגיואַס סאַב-ערייז" שטאַטן אַז איר באַקומען אַ מענגע פון ​​ינטאַדזשערז. געפֿינען די מאַקסימום סומע פון ​​ק-סובאַררייַס אַזוי אַז זייער סומע איז מאַקסימום. די ק-סובאַררייַס קען זיין אָוווערלאַפּינג. מיר דאַרפֿן צו געפֿינען ק-סובאַררייַס אַזוי אַז זייער סומע איז מאַקסימום צווישן אנדערע סובאַררייַס.

בייַשפּיל

ק מאַקסימום סאַמז פון אָוווערלאַפּינג קאַנטיגיואַס סאַב-ערייז

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. קיין אנדערע קאָמבינאַציע וועט געבן אונדז אַ ערגער רעזולטאַט.

צוגאַנג פֿאַר ק מאַקסימום סאַמז פון אָוווערלאַפּינג קאַנטיגיואַס סאַב-ערייז

דער פּראָבלעם פרעגט אונדז צו געפֿינען די ק מאַקסימום סאַמז צווישן אַלע די סאַמז פון אַלע די סובאַרראַ. אַזוי, אויב מיר טראַכטן פון ניצן Kadane ס אַלגערידאַם. מיר וועלן נישט קענען צו סאָלווע די פּראָבלעם. ווייַל Kadane אַלגערידאַם קענען זיין געפֿונען צו געפֿינען די מאַקסימום סומע. אָבער, דאָס קען נישט געפֿינען די רגע מאַקסימום, דריט מאַקסימום און אנדערע. די אַלגערידאַם פון Kadane פאָוקיסיז דער הויפּט אויף דער דערגייונג פון דער ערשטער מאַקסימום און איז נישט דיזיינד צו געפֿינען די ווייַטער מאַקסימום סומע. דאָ מיר מאַכן צוויי ערייז פון minimumKSum און MaximumKSum. מיר וועלן נוצן אַ פּרעפיקס סומע מענגע צו געפֿינען די סומע פון ​​סובאַררייַס פֿאַר דעם קראַנט אינדעקס. סאַם האלט די מינימום סומע פון ​​סובאַררייַס. סומע האלט די מאַקסימום סומע פון ​​סובאַררייַס. איצט פֿאַר יעדער אינדעקס מיר דערהייַנטיקן די מינימאַסקסום און מאַקסימוםקסום ערייז. נאָך דורכפאָר דורך די מענגע, דער ענטפער איז סטאָרד אין מאַקסימום קססום.

קאָדעקס

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

Java קאָד צו געפֿינען ק מאַקסימום סאַמז פון אָוווערלאַפּינג קאַנטיגיואַס סאַב-מענגע

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי: אָ (ק * ן)

ינסערשאַן אין מינימום סקס און ינסערשאַן אין מאַקסימום סקס נעמען אָ (ק) צייט. און מיר טאָן דעם פּראָצעס אין אַ שלייף וואָס איז לופּינג איבער יעדער עלעמענט פון דער מענגע. דעריבער, די קוילעלדיק צייט קאַמפּלעקסיטי איז אָ (ק * ן).

ספעיס קאַמפּלעקסיטי: O (N)

מיר סטאָרד די ינפּוט אין inputArray וואָס איז דער אויבערשטער גרענעץ פֿאַר פּלאַץ. אַזוי דער פּלאַץ קאַמפּלעקסיטי פון די לייזונג איז לינעאַר.