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

uqdfh47h 于 2023-05-27 发布在 Java

关注(0)|答案(2)|浏览(123)

我的方法是计算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;
    
}

Java

来源：https://stackoverflow.com/questions/67657732/maximum-sum-subarray-which-have-same-start-and-end-values

2条答案

按热度按时间

hgc7kmma1#

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

#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;
}

赞(0）回复(0）举报 2023-05-27

5jdjgkvh2#

用于存储代码中最后一个HaspMap的逻辑将存储第一个出现的修改代码：（使用此for代替2和3 for循环）

for(int i=0; i<arr.size(); i++) {
        if(first.get(arr.get(i)) == -1)
            first.replace(arr.get(i), I);
        last.replace(arr.get(i), i);
}

赞(0）回复(0）举报 2023-05-27

我来回答

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

2条答案

相关问题

热门标签

最新问答