Давхардсан дэд массивын хамгийн их нийлбэр


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг CodeNation Dell Facebook-ийн GE Эрүүл мэндийн Google-ийн Qualcomm
Array Динамик програмчлал

Асуудлын мэдэгдэл

"Давхардсан дэд массивуудын хамгийн их K нийлбэрүүд" гэсэн асуудалд танд бүхэл тоон массив өгөгдсөн болно. Тэдний нийлбэр хамгийн их байхаар k дэд дэд массын хамгийн дээд нийлбэрийг ол. Эдгээр k дэд дэд давхцал давхцаж магадгүй юм. Тиймээс k дэд дэд массивуудыг олох хэрэгтэй бөгөөд тэдгээрийн нийлбэр нь бусад дэд массивуудаас хамгийн их байх болно.

Жишээ нь

Давхардсан дэд массивын хамгийн их нийлбэр

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

Тайлбар: Sum = 50 гэсэн дэд массив нь хамгийн их утгатай байна. Үүний дараа, хэрэв бид зүүн эсвэл баруун тийш байвал нийлбэр буурна. Тиймээс, хэрэв бид зүүн чиглэлд шилжвэл. -50 ба 10 нь бие биенээ цуцалдаг тул бид дахин 10-ийн нийлбэрийг авах боломжтой. Гэхдээ хэрэв бид зөв чиглэлд шилжвэл бидний нийлбэр буурсаар л байх болно. Тиймээс, энэ нь бидний авч болох хамгийн сайн хариулт юм.

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

Тайлбар: Энд хоёр тооны аль нэгийг нэгтгэвэл илүү муу шийдэл гарах болно. Тиймээс ганц дугаар сонгох нь илүү дээр байх болно. Тиймээс бид -1 -2 -3 дан тоог сонгох болно. Бусад ямар ч хослол нь бидэнд илүү муу үр дүнг өгөх болно.

Давхардсан дэд массивуудын хамгийн их нийлбэр K-ийн арга

Асуудал нь бүх дэд массивын бүх нийлбэрүүдийн дундаас хамгийн их k-ийг олохыг биднээс хүсдэг. Тиймээс, хэрэв бид ашиглах талаар бодож байвал Каданегийн алгоритм. Бид асуудлыг шийдэж чадахгүй. Учир нь Каданегийн алгоритмаар хамгийн дээд нийлбэрийг олох боломжтой. Гэхдээ энэ нь хоёр дахь дээд, гурав дахь дээд хэмжээ болон бусад зүйлийг олох боломжгүй болно. Каданегийн алгоритм нь эхний дээд хэмжээг олоход голчлон анхаардаг бөгөөд дараагийн хамгийн их дэд массивын нийлбэрийг олохыг зорьдоггүй. Энд бид minimumKSum ба maximumKSum гэсэн хоёр массивыг үүсгэж байна. Бид одоогийн индексийн дэд массивын нийлбэрийг олохын тулд угтварын нийлбэр массивыг ашиглана. Array minimumKSum нь дэд массивын хамгийн бага нийлбэрийг хадгалдаг. Array maximumKSum нь дэд массивын k хамгийн их нийлбэрийг хадгална. Одоо индекс бүрийн хувьд minimumKSum ба maximumKSum массивуудыг шинэчилж байна. Массивыг дайран өнгөрсний дараа хариултыг maximumKSum дотор хадгална.

код

Давхардсан дэд массивын хамгийн их 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

Давхардсан дэд массивын хамгийн их K нийлбэрийг олох 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 (k * N)

MinimumKSum-д оруулах, хамгийн ихдээ Sum-д оруулахад O (k) хугацаа шаардагдана. Бид энэ процессыг массивын элемент тус бүр дээр давталт хийж байгаа давталт дотор хийж байна. Тиймээс цаг хугацааны ерөнхий нарийн төвөгтэй байдал нь юм O (k * n).

Сансрын нарийн төвөгтэй байдал: O (N)

Бид оролтын дээд хязгаарыг тэмдэглэсэн inputArray-д оролтыг хадгалж байна. Тиймээс уусмалын орон зайн нарийн төвөгтэй байдал нь шугаман юм.