sam sam - 2 months ago 39
Java Question

Longest Sub Array

Can anyone suggest a simple solution for the below question.


Longest Sub-array: Find the length of longest contiguous sub-array where the sum of the elements in subarray is less than or equal to "k".


Inputs are:
array
and
k
.

Example:

Array = {1,2,3}, k = 3


Output:


2


Explanation:


Sub arrays : {1},{2},{3},{1,2},{2,3},{1,2,3}

{1,2} => max length = 2; 1+2 = 3 (<=k);

Answer

An efficient method is to use dynamic programming, to reduce the number of summation operations. For example, if you sum (1 + 2) = 3, you don't wanna sum (1 + 2 + 3) = 6 again, you only wanna sum (3 + 3) = 6 (where the first 3 has already been calculated and saved into a hashmap). In this solution, the hashmap represents the sum from index i to index j, in the format <i, <j, sum>>. So you have all sums starting from index i stored in the inner hashmap. Note that you could also use a 2D array instead of the nested hashmap structure, but for very large data, you are likely to get an out-of-memory exception while initializing that array.

    static int maxLength(int[] a, int k) {
        Map<Integer, Map<Integer, Long>> map = new HashMap<Integer, Map<Integer, Long>>();

        int maxLength = 0;
        for(int i = 0; i < a.length - 1; i++) {
            Map<Integer, Long> map2 = new HashMap<Integer, Long>();
            map2.put(i, (long)a[i]);
            map.put(i, map2);
            if(a[i] == k) {
                maxLength = 1;
            }
        }

        for(int l = 2; l <= a.length; l++) {
            long sum = 0;
            for(int i = 0; i <= a.length - l; i++) {
                int j = i + l - 1;
                Map<Integer, Long> map2 = map.get(i);
                sum = map2.get(j - 1) + a[j];
                map2.put(j, sum);

                if(sum <= k)
                {
                    if(l > maxLength) {
                        maxLength = l;
                    }
                }
            }
        }

        return maxLength;
    }
Comments