Максимална сума на подменъла, с изключение на определени елементи



Често задавани в Аколит CodeNation Directi JP Morgan Qualcomm
Array Двоично търсене Динамично програмиране Технически скрипт

Декларация за проблема

Даден ни е масив и трябва да намерим максимална сума от подмасив, с изключение на определени елементи. Тоест, трябва да намерим максималната сума на подмасив, така че разглежданият от нас подмасив да не съдържа елементите, за които се казва, че трябва да бъдат изключени.

Пример за максимална сума на подменъла с изключение на определени елементи

Максимална сума на подменъла, с изключение на определени елементи

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

Обяснение: Тук не можем да изберем подмасив, така че подмасивът да съдържа изключените елементи. По този начин можем да изберем или 1, или 4. Но тъй като 4 е по-голямо от 1, 4 е нашият отговор. Проблемът с Ans е искането за подмасив вместо подпоследователност. Иначе щяхме да вземем и 1 в нашия отговор.

 

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

Обяснение: Тук не е трябвало да избираме отрицателен елемент и не можем да вземем 10 в подмасив. Така че отново имаме два избора, или изберете 1 или 2. Тъй като 2> 1, отговорът е 2.

 

Подход за намиране на максимална сума от подмасив, с изключение на определени елементи

Наивен подход

Можем лесно да разгледаме целия подмасив и след това да проверим дали подмасивът съдържа елемент, който трябва да бъде изключен. Ако не съдържа такъв елемент, ние просто намираме сумата и актуализираме отговора си. Но този подход не е ефективен. Ефективен подход би бил, ако използвахме Алгоритъм на Kadane за да намерите максималния подмасив. Но ние използваме Kadane's само в онези части, които не съдържат елементите, които трябва да бъдат изключени. Сега проблемът е как да открием дали трябва да изключим елемент или не. Можем да преминем през масива от елементи, които трябва да бъдат изключени. И ако масивът съдържа текущия елемент, ние не го избираме, иначе ще продължим напред. Но този подход може да бъде допълнително оптимизиран, което е описано в раздела за ефективен подход.

Ефективен подход

Вече обсъдихме, че ще използваме алгоритъма на Kadane, за да намерим сумата на подмасива. Винаги, когато текущият елемент е един от елементите, които трябва да бъдат изключени. Ние просто игнорираме този елемент и продължаваме напред, докато актуализираме currentSum до 0. Сега все още има проблем да разберем дали текущият елемент трябва да бъде изключен или не? За да проверите дали елементът трябва да бъде изключен или не. Използваме хеш набор или unordered_set. Ако комплектът съдържа текущия елемент, го пропускаме, иначе продължаваме. Така че, за да бъде ясно, този unordered_set съдържа елементите, които трябва да бъдат изключени.

Код за намиране на максимална сума на подменъла, с изключение на определени елементи

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

 

Java код

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_set или HashSet за съхраняване на елементите, които трябва да бъдат изключени. Имаме алгоритъм с линейна времева сложност на O (N).

Сложност на пространството: НА)

HashSet или unrdered_set отнема памет, пропорционална на броя двойки ключ-стойност и освен това, ние използвахме един масив. По този начин имаме космическа сложност на O (N).