Maximum sum subarray which have same start and end values

Question

My approach is to calculate the first and last occurrence of every element in HashMap. And then maintain a prefix sum of the array. Then calculating the sum on the basis of first and last occurrence. My code is running fine in sample test cases. But getting failed in hidden one.

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

You can use this approach and run this code, It may pass the hidden test case.

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