nghi1129
BAN USERHere's an O(n) solution:
public static int longestAltSeqStart(int [] input)
{
if (input == null || input.length == 1) // must be 2 or more to have alternating?
{
return -1;
}
int resultIndex = 0;
int curAltIndex = 0;
int lastAltLength = 1;
int curAltLength = 1;
int lastDirection = input[1] - input[0]; // increase (+), decrease (-), neither (0)
for (int i = 1; i < input.length - 1; i++)
{
int curDir = input[i + 1] - input[i];
if (curDir == 0) // end of a seq
{
if (curAltLength > lastAltLength)
{
resultIndex = curAltIndex;
lastAltLength = curAltLength;
System.out.println("L1: " + lastAltLength);
}
curAltLength = 0;
curAltIndex = -1;
System.out.println("Index: " + curAltIndex);
}
else if (lastDirection == 0 || sameDir(curDir, lastDirection)) // end of seq, start of new seq
{
if (curAltLength > lastAltLength)
{
resultIndex = curAltIndex;
lastAltLength = curAltLength;
System.out.println("L2: " + lastAltLength);
}
curAltLength = 1;
curAltIndex = i;
System.out.println("Index: " + curAltIndex);
}
else // continuing seq
{
curAltLength++;
}
lastDirection = curDir;
}
System.out.println("R Index: " + resultIndex);
System.out.println("R Length: " + lastAltLength);
return resultIndex;
}
public static boolean sameDir(int dir1, int dir2)
{
return (dir1 < 0 && dir2 < 0) || (dir1 > 0 && dir2 > 0);
}
@Naz20 - Yep, totally agreed. This is basically right in the middle of a merge-sort operation. At the base of the recursion of merge sorts, you have L.length lists of size 1, and as they merge, somewhere up the recursion tree you have x sorted lists of size L.length / x. When x == 1 (top of recursion tree), you have L fully sorted.
- nghi1129 April 01, 2016
Success time: 0.11 memory: 320512 signal:0
- nghi1129 April 06, 2016Group: G1
MemberOf: G4, Members: G2, G3, G6,
Group: G2
MemberOf: G1, Members: G4, U2,
Group: G3
MemberOf: G1, G3, Members: G3, G5,
Group: G4
MemberOf: G2, Members: G1, U1,
Group: G5
MemberOf: G3, Members: U2, G6,
Group: G6
MemberOf: G1, G5, Members: U3,