_999MSOnlineAssessment.java

package com.fishercoder.solutions;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class _999MSOnlineAssessment {
    /**
     * Given an array, return the start/end indices of the contiguous subarray that have the largest sum.
     * <p>
     * Note:
     * 1. There could be multiple subarrays, return all of the indices.
     */

    public static void main(String... args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, -1, -3, -6, 3, 2, -4};
//        int[] nums = new int[]{-1, -2, 1,2,3};
//        int[] nums = new int[]{-1, -2, 1,2,3,-1, -2};
//        List<int[]> result = subarraySum_v2(nums);

    }

    public static List<int[]> subarraySum_v2(int[] nums) {
        int[] preSums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            preSums[i] = preSums[i - 1] + nums[i - 1];
        }
        TreeMap<Integer, List<int[]>> preSum = new TreeMap(Collections.reverseOrder());
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < i - 1; j++) {
                int sum = preSums[i] - preSums[j];
                if (!preSum.containsKey(sum)) {
                    List<int[]> value = new ArrayList<>();
                    value.add(new int[]{j, i - 1});
                    preSum.put(sum, value);
                } else {
                    List<int[]> value = preSum.get(sum);
                    value.add(new int[]{j, i - 1});
                    preSum.put(sum, value);
                }
            }
        }
        Map.Entry<Integer, List<int[]>> firstEntry = preSum.firstEntry();
        return firstEntry.getValue();
    }
}