حداکثر جمع زیرمجموعه به استثنای برخی عناصر



اغلب در همبستگی CodeNation دیرتی JP مورگان سامسونگ
صف جستجوی دودویی برنامه نویسی پویا نویسنده فنی

بیان مسأله

به ما یک آرایه داده می شود و ما باید حداکثر جمع زیر مجموعه را به استثنای عناصر خاص پیدا کنیم. به این معنی که ما باید حداکثر مجموع زیرآرایه را پیدا کنیم تا زیر مجموعه ای که در نظر می گیریم حاوی عناصری نباشد که گفته می شود مستثنی هستند.

نمونه ای از حداکثر مجموع زیرآرایه به استثنای عناصر خاص

حداکثر جمع زیرمجموعه به استثنای برخی عناصر

Array = {1,2,3,4,5}
Elements to be excluded = {2,3,5}
4

توضیحات: در اینجا ، ما نمی توانیم زیر مجموعه ای را انتخاب کنیم که زیر مجموعه شامل عناصر مستثنی باشد. بنابراین می توانیم 1 یا 4 را انتخاب کنیم. اما از آنجا که 4 بزرگتر از 1 است ، 4 پاسخ ما است. مشکل Ans درخواست زیرآرایه به جای Submission است. در غیر اینصورت ما نیز در جواب خود 1 می گرفتیم.

 

Array = {1,-1,10,-6,2}
Elements to be excluded = {10}
2

توضیح: در اینجا ، ما نباید هیچ عنصر منفی را انتخاب می کردیم ، و نمی توانیم 10 مورد را زیر مجموعه قرار دهیم. بنابراین دوباره ، ما دو گزینه داریم ، یا 1 یا 2 را انتخاب کنید. از آنجا که 2> 1 ، پاسخ 2 است.

 

رویکرد برای یافتن حداکثر مجموع زیر مجموعه به استثنای عناصر خاص

رویکرد ساده لوحانه

ما می توانیم به راحتی تمام زیرشاخه ها را در نظر بگیریم ، و سپس بررسی کنیم که آیا زیر مجموعه ها عنصری را حذف می کند که باید حذف شود. اگر چنین عنصری را شامل نشود ، ما فقط جمع را پیدا می کنیم و پاسخ خود را به روز می کنیم. اما این روش کارآمد نیست. اگر ما استفاده می کردیم ، رویکردی کارآمد بود الگوریتم Kadane برای پیدا کردن حداکثر زیر مجموعه. اما ما فقط Kadane را در قسمتهایی اجرا می کنیم که حاوی عناصر قابل حذف نیستند. حال ، مسئله این است که چگونه می توانیم عنصری را حذف کنیم یا خیر. ما می توانیم روی آرایه ای از عناصر که باید حذف شوند حلقه بزنیم. و اگر آرایه حاوی عنصر فعلی باشد ، ما آن را انتخاب نمی کنیم و به جلو حرکت می کنیم. اما این رویکرد می تواند بیشتر بهینه شود ، که در بخش رویکرد کارآمد گفته شده است.

رویکرد کارآمد

ما قبلاً بحث کردیم که از الگوریتم Kadane برای یافتن مجموع زیر مجموعه استفاده خواهیم کرد. هر زمان که عنصر فعلی یکی از عناصر حذف شود. ما فقط آن عنصر را نادیده می گیریم و جلو می رویم ، در حالی که currentSum را به 0 می رسانیم. حال ، هنوز یک مشکل وجود دارد که بفهمیم آیا عنصر فعلی باید حذف شود یا خیر؟ برای بررسی اینکه آیا این عنصر باید حذف شود یا خیر. ما از یک مجموعه هش یا مجموعه غیر مرتب استفاده می کنیم. اگر مجموعه حاوی عنصر فعلی باشد ، ما از آن رد می شویم و ادامه می دهیم. بنابراین ، برای اینکه روشن شود ، این مجموعه غیر مرتب حاوی عناصری است که باید حذف شوند.

کد را پیدا کنید تا حداکثر جمع زیر مجموعه را به استثنای عناصر خاص پیدا کنید

کد C ++

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

int main(){
  int testCases;cin>>testCases;
  while(testCases--){
    int inputSize;cin>>inputSize;
    int input[inputSize];
    for(int i=0;i<inputSize;i++)
      cin>>input[i];
    int excludedElementsSize;cin>>excludedElementsSize;
    unordered_set<int> excludedElements;
    for(int i=0;i<excludedElementsSize;i++){
      int excludedElement;cin>>excludedElement;
      excludedElements.insert(excludedElement);
    }

    int currentSum = 0, maximumSum = 0;

    for(int i=0;i<inputSize;i++){
      if(excludedElements.count(input[i])){
        currentSum = 0;
      } else {
          currentSum = max(currentSum + input[i], input[i]);
          maximumSum = max(currentSum, maximumSum);
      }
    }
    cout<<maximumSum<<endl;
  }
}
1
5
1 2 3 4 5
3
2 3 4
4

 

کد جاوا

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
    	int testCases = sc.nextInt();
    	while(testCases-- > 0){
    		int inputSize = sc.nextInt();
    		int input[] = new int[inputSize];
    		for(int i=0;i<inputSize;i++)
    		    input[i] = sc.nextInt();
    		int excludedElementsSize = sc.nextInt();
    		HashSet<Integer> excludedElements = new HashSet<Integer>();
    		for(int i=0;i<excludedElementsSize;i++){
    		    int excludedElement = sc.nextInt();
    	       	    excludedElements.add(excludedElement);
    		}
    
    		int currentSum = 0, maximumSum = 0;
    
    		for(int i=0;i<inputSize;i++){
    	            if(excludedElements.contains(input[i])){
    			currentSum = 0;
                    } else {
                        currentSum = Math.max(currentSum + input[i], input[i]);
                        maximumSum = Math.max(currentSum, maximumSum);
                    }
    		}
    
    		System.out.println(maximumSum);
        }
    }
}
1
5
1 2 3 4 5
3
2 3 4
4

 

تحلیل پیچیدگی

پیچیدگی زمان: بر)

از آنجا که ما به راحتی آرایه را رد کرده ایم و فقط از یک مجموعه unordered_ یا HashSet برای ذخیره عناصر مورد استفاده استفاده کرده ایم. ما یک الگوریتم با پیچیدگی زمانی خطی O (N) داریم.

پیچیدگی فضا: بر)

یک مجموعه HashSet یا unruled_ متناسب با تعداد جفت کلید-مقدار حافظه را می گیرد و غیر از این ، ما از یک آرایه استفاده کرده ایم. بنابراین ما دارای پیچیدگی فضایی O (N) هستیم.