排除某些元素的最大子数组总和



经常问 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)。