-
Notifications
You must be signed in to change notification settings - Fork 0
/
SubrangeDifference.java
65 lines (53 loc) · 1.74 KB
/
SubrangeDifference.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package com.sushantjhingan;
/**
* QUESTION:
*
* Given an array (A) of length N and a window of length K such that k<=N,
* find the difference between increasing contiguous subsets and decreasing contiguous subsets
* for each possible window in that array A.
*
* @author Sushant Jhingan
*
*/
public class SubrangeDifference {
public static void main(String[] args) {
String input = "188930 144123 201345 154243 164243";
int K = 5;
String[] inputArray = input.split(" ");
int N = inputArray.length;
calculateSubrangeDiff(K, inputArray, N);
}
private static void calculateSubrangeDiff(int K, String[] inputArray, int N) {
for(int i = 0; i< N; i++ ){
if(i+K <= inputArray.length){
System.out.println(calDifference(i, K, inputArray));
}else{
break;
}
}
}
private static int calDifference(int start, int length, String[] inputArray) {
int increasingCount = 0;
int decreasingCount = 0;
int ilen = 1;
int dlen = 1;
for(int i= start; i< start+length-1; i++){
if (Integer.parseInt(inputArray[i + 1]) > Integer.parseInt(inputArray[i])){
ilen++;
decreasingCount += (((dlen - 1) * dlen) / 2);
dlen = 1;
}else if (Integer.parseInt(inputArray[i + 1]) < Integer.parseInt(inputArray[i]))
{
increasingCount += (((ilen - 1) * ilen) / 2);
ilen = 1;
dlen++;
}
}
// LOGIC: a sorted subarray of length ‘len’ adds len*(len-1)/2 to result
if (ilen > 1)
increasingCount += (((ilen - 1) * ilen) / 2);
if (dlen > 1)
decreasingCount += (((dlen - 1) * dlen) / 2);
return increasingCount - decreasingCount ;
}
}