tr030114
BAN USERHere is my solution without extraspace and O(n) running time.
The idea is you scan through the array and change the minimum and check if the difference is with -1 -> 0 -> 1. If the difference is greater than 1 you can safely skip through until you reach the maximum number at which point you repeat the same process.
I could probably do away with couple variables.
private static void printSubset(int[] a)
{
int size = a.length;
int sequenceStart = 0, sequenceEnd = 0;
int finalSequenceStart = 0, finalSequenceEnd = -1;
int min = a[0],max = a[0];
for(int j = 0;j< size; j++)
{
if((a[j]-min <= 1) && (a[j] - min >= -1))
{
sequenceEnd = j;
if(a[j] < min)
min = a[j];
if((finalSequenceEnd-finalSequenceStart)< (sequenceEnd-sequenceStart))
{
finalSequenceEnd = sequenceEnd;
finalSequenceStart = sequenceStart;
}
}
else
{
min = a[j];
max = a[j];
sequenceStart = j;
sequenceEnd = j;
}
}
System.out.println("Sequence Start is: "+finalSequenceStart+" Sequence End is:" +finalSequenceEnd);
}
Well, first of all we need to ask followup questions. How does it work in its current state. Why is it assumed that it can be optimized. What are the common complaints from users.
- tr030114 March 09, 2015Based on this historical data we can tackle the problem areas.
For example, if the tenants on the top half of floors complain that it stops frequently on the bottom half, then you probably are looking at dividing the elevator system between top half and bottom half.
Top half gets two and bottom half get the remaining two elevators.
You get the idea.