We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximum Subarray Sum
  5. Discussions

Maximum Subarray Sum

  • rajivaiyer
     + 0 comments

    My Java 8 solution, passing all test-cases, for Max Score of 60

    The idea is to do a "continuous trailing prefix modulo sum" as we iterate through the array, while comparing that with the maxModSum that we have seen so far & updating that as required. We maintain a prefixSumTreeSet to keep track of all the distinct prefixSums we have seen so far. We check if we have encountered a prefixSum that's higher than the curPrefixSum, and if so: then we use the higherPrefixTS value to update maxModSum as required.

    By using this approach, we only need to loop through the array once from start to finish (costing O(n) time). In each iteration, we spend some time going through the prefixSumTreeSet to locate the "higher" element, or to add a new element to the TreeSet (costing O(log(n)) time. This results in an overall Time Complexity of O(n * log(n)).

        public static long maximumSum(List<Long> a, long m) {
        // Write your code here
        long maxModSum = 0;
        long curPrefixSum = 0;

        TreeSet<Long> prefixSumTreeSet = new TreeSet<>();
        prefixSumTreeSet.add(0L);

        for (int aIdx = 0 ; aIdx < a.size() ; aIdx++) {

            curPrefixSum = ((curPrefixSum + a.get(aIdx) % m + m) % m);

            maxModSum = Math.max(maxModSum, curPrefixSum);

            Long higherPrefixTS = prefixSumTreeSet.higher(curPrefixSum);

            // System.err.println("aIdx=" + aIdx + " | a[" + aIdx + "]=" + a.get(aIdx) + 
            //                    " | curPrefixSum=" + curPrefixSum + " | maxModSum=" + 
            //                    maxModSum + " | higherPrefixTS=" + higherPrefixTS + 
            //                    " | prefixSumTreeSet=" + prefixSumTreeSet);

            if (higherPrefixTS != null) {
                maxModSum = Math.max(maxModSum, 
                                     ((curPrefixSum - higherPrefixTS + m) % m));
            }

            prefixSumTreeSet.add(curPrefixSum);

            // System.err.println("aIdx=" + aIdx + " | maxModSum=" + maxModSum + 
            //                    " | prefixSumTreeSet=" + prefixSumTreeSet);
        }

        return maxModSum;
    }