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

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

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

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

## 查找不包括某些元素的最大子數組總和的代碼

### 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`

## 複雜度分析

### 空間複雜度： 上）

HashSet或unrdered_set佔用的內存與鍵值對的數量成正比，除此之外，我們只使用了一個數組。 因此，我們的空間複雜度為O（N）。