sam - 1 year ago 132

Java Question

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`

`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 Source

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