ਓ ਕੇ ਓਵਰਲੈਪਿੰਗ ਸੰਖੇਪ ਉਪ-ਐਰੇ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੋਡਨੇਸ਼ਨ ਡੈੱਲ ਫੇਸਬੁੱਕ GE ਹੈਲਥਕੇਅਰ ਗੂਗਲ Qualcomm
ਅਰੇ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਕੇ ਓਵਰਲੈਪਿੰਗ ਕੰਟੀਗੁਇਸ ਸਬ-ਐਰੇ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮ" ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਪੂਰਨ ਅੰਕ ਦੀ ਇੱਕ ਲੜੀ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ. ਕੇ-ਸਬਨਰਾਇਆਂ ਦੀ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮ ਦਾ ਪਤਾ ਲਗਾਓ ਕਿ ਉਨ੍ਹਾਂ ਦੀ ਜੋੜ ਵੱਧ ਤੋਂ ਵੱਧ ਹੋਵੇ. ਇਹ ਕੇ-ਸਬਰੇਅਸ ਓਵਰਲੈਪਿੰਗ ਹੋ ਸਕਦੇ ਹਨ. ਇਸ ਲਈ, ਸਾਨੂੰ ਕੇ-ਸਬਰੇਅਸ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਕਿ ਉਹਨਾਂ ਦੀ ਰਕਮ ਹੋਰ ਉਪਨਗਰਾਂ ਵਿਚ ਵੱਧ ਤੋਂ ਵੱਧ ਹੋਵੇ.

ਉਦਾਹਰਨ

ਓ ਕੇ ਓਵਰਲੈਪਿੰਗ ਸੰਖੇਪ ਉਪ-ਐਰੇ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮ

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 ਦੀ ਚੋਣ ਕਰਾਂਗੇ. ਕੋਈ ਹੋਰ ਸੁਮੇਲ ਸਾਨੂੰ ਮਾੜਾ ਨਤੀਜਾ ਦੇਵੇਗਾ.

ਓਵਰਲੈਪਿੰਗ ਸੰਖੇਪ ਉਪ-ਐਰੇ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮਾਂ ਲਈ ਪਹੁੰਚ

ਸਮੱਸਿਆ ਸਾਨੂੰ ਸਾਰੇ ਸਬਰੇਅ ਦੇ ਸਾਰੇ ਜੋੜਾਂ ਵਿਚ ਕੇ ਕੇ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮਾਂ ਲੱਭਣ ਲਈ ਕਹਿੰਦੀ ਹੈ. ਇਸ ਲਈ, ਜੇ ਅਸੀਂ ਇਸ ਦੀ ਵਰਤੋਂ ਬਾਰੇ ਸੋਚਦੇ ਹਾਂ ਕਡਨੇ ਦਾ ਐਲਗੋਰਿਦਮ. ਅਸੀਂ ਸਮੱਸਿਆ ਦਾ ਹੱਲ ਨਹੀਂ ਕਰ ਸਕਾਂਗੇ. ਕਿਉਂਕਿ ਕੈਡੇਨ ਦੀ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮ ਲੱਭਣ ਲਈ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ. ਪਰ ਇਹ ਦੂਜਾ ਅਧਿਕਤਮ, ਤੀਜਾ ਅਧਿਕਤਮ ਅਤੇ ਹੋਰਾਂ ਨੂੰ ਨਹੀਂ ਲੱਭ ਸਕੇਗਾ. ਕੇਡਨੇ ਦਾ ਐਲਗੋਰਿਦਮ ਮੁੱਖ ਤੌਰ ਤੇ ਪਹਿਲੀ ਅਧਿਕਤਮ ਨੂੰ ਲੱਭਣ ਤੇ ਕੇਂਦ੍ਰਤ ਕਰਦਾ ਹੈ ਅਤੇ ਅਗਲੀ ਵੱਧ ਤੋਂ ਵੱਧ ਸਬਰੇਅ ਜੋੜ ਨੂੰ ਲੱਭਣ ਦਾ ਉਦੇਸ਼ ਨਹੀਂ ਰੱਖਦਾ. ਇੱਥੇ ਅਸੀਂ ਮਿਨੀਮਟ ਕੇਸਮ ਅਤੇ ਮੈਕਸਿਮੈਕਸ ਕੇਸਮ ਦੀਆਂ ਦੋ ਐਰੇ ਬਣਾਉਂਦੇ ਹਾਂ. ਮੌਜੂਦਾ ਇੰਡੈਕਸ ਲਈ ਉਪਨਗਰਾਂ ਦੇ ਜੋੜ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਅਸੀਂ ਅਗੇਤਰ ਦੀ ਰਕਮ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ. ਐਰੇ ਨਿ minimumਨਤਮ ਕੇਸਮ ਸਬ ਕਿਨਾਰੇ ਦੀ ਘੱਟੋ ਘੱਟ ਜੋੜ ਰੱਖਦਾ ਹੈ. ਐਰੇ ਮੈਕਸਿਮਲਕਮਸੁਮ ਕੇ ਸਬਅਰੇਅਸ ਦੀ ਅਧਿਕਤਮ ਸੰਖਿਆ ਰੱਖਦਾ ਹੈ. ਹੁਣ ਹਰੇਕ ਇੰਡੈਕਸ ਲਈ, ਅਸੀਂ ਘੱਟੋ ਘੱਟ ਕੇਸਮ ਅਤੇ ਅਧਿਕਤਮ ਕੇਸਮ ਐਰੇ ਨੂੰ ਅਪਡੇਟ ਕਰਦੇ ਹਾਂ. ਐਰੇ ਵਿੱਚੋਂ ਲੰਘਣ ਤੋਂ ਬਾਅਦ, ਉੱਤਰ ਅਧਿਕਤਮ ਕੇਸਮ ਵਿੱਚ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ.

ਕੋਡ

ਓ + ਓਵਰਲੈਪਿੰਗ ਸੰਖੇਪ ਉਪ-ਐਰੇ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਰਕਮਾਂ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਸੀ ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ: ਓ (ਕੇ * ਐਨ)

ਘੱਟੋ ਘੱਟ ਕੇਸਮ ਵਿੱਚ ਪਾਉਣ ਅਤੇ ਵੱਧ ਤੋਂ ਵੱਧ ਕੇਸਮ ਵਿੱਚ ਪਾਉਣ ਵਿੱਚ ਓ (ਕੇ) ਸਮਾਂ ਲਗਦਾ ਹੈ. ਅਤੇ ਅਸੀਂ ਇਸ ਪ੍ਰਕਿਰਿਆ ਨੂੰ ਇੱਕ ਲੂਪ ਦੇ ਅੰਦਰ ਕਰ ਰਹੇ ਹਾਂ ਜੋ ਐਰੇ ਦੇ ਹਰ ਤੱਤ ਉੱਤੇ ਲੂਪ ਕਰ ਰਹੀ ਹੈ. ਇਸ ਲਈ, ਸਮੁੱਚੇ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਹੈ ਓ (ਕੇ * ਐਨ).

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ: ਓ (ਐਨ)

ਅਸੀਂ ਇਨਪੁਟ ਅਰੇ ਵਿੱਚ ਇਨਪੁਟ ਸਟੋਰ ਕਰ ਰਹੇ ਹਾਂ ਜੋ ਸਪੇਸ ਲਈ ਉਪਰਲੇ ਬਾਉਂਡ ਨੂੰ ਨਿਸ਼ਾਨਬੱਧ ਕਰਦੀ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਘੋਲ ਦੀ ਸਪੇਸ ਗੁੰਝਲਤਾ ਰੇਖਿਕ ਹੈ.