排除某些元素的最大子數組總和



經常問 ol石 編碼國家 指令 JP摩根 高通公司
排列 二元搜尋 動態編程 技術編劇

問題陳述

給定一個數組,我們需要找到不包括某些元素的最大子數組總和。 也就是說,我們需要找到子數組的最大和,以使我們正在考慮的子數組不包含被告知要排除的元素。

排除某些元素的最大子數組總和的示例

排除某些元素的最大子數組總和

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。 現在,問題是如何找到是否需要排除某個元素。 我們可以遍歷要排除的元素數組。 如果數組包含當前元素,則不選擇它,否則我們將繼續。 但是,可以在“有效方法”部分中對此方法進行進一步優化。

高效方法

我們已經討論過,我們將使用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)。