具有相同起始值和结束值的最大和子数组

Question

我的方法是计算HashMap中每个元素的第一次和最后一次出现。然后维护数组的前缀和。然后根据第一次和最后一次出现计算总和。我的代码在样本测试用例中运行没问题。但是隐藏的失败了

public static int maximumSum(ArrayList<Integer>arr) {

    LinkedHashMap<Integer, Integer> first = new LinkedHashMap<>();
    LinkedHashMap<Integer, Integer> last = new LinkedHashMap<>();
    ArrayList<Integer> preSum = new ArrayList<>();
    int curSum = 0;
    int maxSum = 0;
    
    preSum.add(arr.get(0));
    
    for(int x : arr) {
        first.put(x, -1);
        last.put(x, -1);
    }
    
    for(int i=0; i<arr.size(); i++) {
        if(first.get(arr.get(i)) == -1)
            first.replace(arr.get(i), i);
    }
    for(int i=arr.size()-1; i>=0; i--) {
        if(last.get(arr.get(i)) == -1)
            last.replace(arr.get(i), i);
    }
    
    for(int i=1; i<arr.size(); i++)
        preSum.add(arr.get(i)+preSum.get(i-1));
        
    for(Map.Entry<Integer, Integer> e : first.entrySet()) {
        curSum = 0;
        
        int f = e.getValue();
        int l = last.get(e.getKey());
        
        if(f == 0 || l == 0)
            curSum = preSum.get(l);
        else
            curSum = preSum.get(l)-preSum.get(f-1);

        if(curSum > maxSum)
            maxSum = curSum;
    }
    
    return maxSum;
    
}

Answer 1

你可以使用这种方法和运行这段代码，它可能会通过隐藏的测试用例。

#include <bits/stdc++.h>
using namespace std;
int maxValue(int arr[], int n) {
   unordered_map<int, int> startIndex, endIndex;
   int sumArr[n];
   sumArr[0] = arr[0];
   for (int i = 1; i < n; i++) {
      sumArr[i] = sumArr[i − 1] + arr[i];
      if (startIndex[arr[i]] == 0)
         startIndex[arr[i]] = i;
      endIndex[arr[i]] = i;
   }
   int maxSum = 0;
   for (int i = 0; i < n; i++) {
      int left = startIndex[arr[i]];
      int right = endIndex[arr[i]];
      maxSum = max(maxSum, sumArr[right] − sumArr[left − 1]);
   }
   return maxSum;
}
int main() {
   int arr[] = { 2, 1, 3, 5, 6, 2, 4, 3 };
   int n = sizeof(arr) / sizeof(arr[0]); 
   cout<<"The maximum sum subarray such that start and end values are same is "<<maxValue(arr, n);
   return 0;
}

具有相同起始值和结束值的最大和子数组

Maximum sum subarray which have same start and end values

java

hashmap

sub-array