Google Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
void maxAlternatingSubsequence(int arg[] , int aLength){
if(arg == NULL||aLength == 0 || aLength == 1) return;
// we will store the length of current alternating subsequence here. [ for each index ]
int* results = new int[aLength];
results[0] = 1;
// this will have a value of 0, or 1.
int lastRelation = -1; // 0 < , 1 >
// browse through the entire List.
for(int i=1; i<aLength; i++){
if((arg[i] > arg[i-1] && ( lastRelation == 0 || lastRelation == -1))
||(arg[i] < arg[i-1] && ( lastRelation == 1 || lastRelation == -1))
){
// does not matter just add it.
results[i]=results[i-1]+1;
if(lastRelation == -1){
lastRelation = 1;
}else if(lastRelation == 0) {
lastRelation =1;
}else {
lastRelation = 0;
}
}else {
results[i]=1;
}
}
// get the max out of the list.
for(int i=0; i<aLength; i++){
printf("%d\n",results[i]);
}
}
void maxAlternatingSubsequence(int arg[] , int aLength){
if(arg == NULL||aLength == 0 || aLength == 1) return;
// we will store the length of current alternating subsequence here. [ for each index ]
int* results = new int[aLength];
results[0] = 1;
// this will have a value of 0, or 1.
int lastRelation = -1; // 0 < , 1 >
// browse through the entire List.
for(int i=1; i<aLength; i++){
if((arg[i] > arg[i-1] && ( lastRelation == 0 || lastRelation == -1))
||(arg[i] < arg[i-1] && ( lastRelation == 1 || lastRelation == -1))
){
// does not matter just add it.
results[i]=results[i-1]+1;
if(lastRelation == -1){
lastRelation = 1;
}else if(lastRelation == 0) {
lastRelation =1;
}else {
lastRelation = 0;
}
}else {
results[i]=1;
}
}
for(int i=0; i<aLength; i++){
printf("%d\n",results[i]);
}
}
void maxAlternatingSubsequence(int arg[] , int aLength){
if(arg == NULL||aLength == 0 || aLength == 1) return;
// we will store the length of current alternating subsequence here. [ for each index ]
int* results = new int[aLength];
results[0] = 1;
// this will have a value of 0, or 1.
int lastRelation = -1; // 0 < , 1 >
// browse through the entire List.
for(int i=1; i<aLength; i++){
if((arg[i] > arg[i-1] && ( lastRelation == 0 || lastRelation == -1))
||(arg[i] < arg[i-1] && ( lastRelation == 1 || lastRelation == -1))
){
// does not matter just add it.
results[i]=results[i-1]+1;
if(lastRelation == -1){
lastRelation = 1;
}else if(lastRelation == 0) {
lastRelation =1;
}else {
lastRelation = 0;
}
}else {
results[i]=1;
}
}
for(int i=0; i<aLength; i++){
printf("%d\n",results[i]);
}
}
Shouldn't max len for {1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45} be 10?
2- 51 - 50 -60 - 55 -70-68-75-12-45
Problem could be solved using dynamic programming technicue for O(n^2) time complexity.
We define two recursive function rise[i] = Max (fall[j] ) + 1 for j < i
and fall[i] = Max (rise[j] ) + 1 for j < i. rise[i] means length of longest subsequence that end in index i with rise, fall[i] is the opposite. We can store current subsequence in additional memory while we calculate up and fall function.
Coudn't edit my previous reply. Hence, adding it as a new post:
Made edits to the code, to remove redundancy
Assumption: the question has a typo in the explanation:
Should be " [a1, a2, a3, ..., ak] where a1 > a2, a2 < a3, a3 > a4, ..." for the graph to look like \/\/\/
Algorithm:
Keep track of a boolean: isLesser. the boolean is relative to current element in consideration
if the sequence is alternating:
a1> a2 => isLesser = false
a2 < a3 => isLesser = true
a3 > a4 => isLesser = false
and so on
Hence for the current pair to be counted in the alternating subsequence, the previous value of isLesser should be the inverse of what the current isLesser is expected to be. If so increment the the length of the subsequence, else
count the length of the currentSubSequence length into the max
Time Complexity: O(n)
Space Complexity: O(1)
Coded in Java:
public class Main {
public static void main(String[] args) {
int[] input = {1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45}; //MaxSubLen:9 (2, 51, 50, 60, 55, 70, 68, 80, 76)
//int[] input = {1, 2, 51, 50, 45, 55, 54, 68, 66, 76, 75, 12, 45}; //MaxSubLen:8 (50, 45, 55, 54, 68, 66, 76, 75)
//int[] input = {1, 2, 3, 4, 5, 6, 70}; //MaxSubLen:2 (1, 2)
//int[] input = {1, 1, 1, 1, 1, 2}; //MaxSubLen: 2 (1, 2)
//int[] input = {3, 3, 3, 3, 3, 2}; //MaxSubLen: 2 (3, 2)
//int[] input = {1, 1, 1, 1, 1, 1}; //MaxSubLen: 1 (1)
//int[] input = {50, 45, 51, 48, 62, 55, 73}; //MaxSubLen:7 (50, 45, 51, 48, 62, 55, 73)
//int[] input = {1, 1, 1, 2, 1, 1, 1}; //MaxSubLen:3 (1, 2, 1)
//int[] input = {2, 2, 2, 1, 2, 2, 2}; //MaxSubLen:3 (2, 1, 2)
boolean isLesser;
int maxLength = 1;
int tmpLength = 1;
int size = input.length;
if (size < 2) {
System.out.println("MaxSubLen: 1");
}
if (input[0] < input[1]) {
isLesser = true;
} else if (input[0] > input[1]) {
isLesser = false;
} else {
isLesser = true;
tmpLength = maxLength = 0;
}
for (int i = 1; i < size - 1; i++) {
boolean isEnd = false;
if (input[i] == input[i + 1]) {
isEnd = true;
isLesser = true;
} else if (input[i] > input[i + 1]) {
if (!isLesser) {
isEnd = true;
}
isLesser = false;
} else {
if (isLesser) {
isEnd = true;
}
isLesser = true;
}
if (!isEnd) {
tmpLength++;
} else {
// we have hit an anomaly in the pattern,
// store the current subsequence length length into max and reset all the values
if (tmpLength > maxLength) {
maxLength = tmpLength;
}
// Reset the values to start again the count
tmpLength = (input[i] == input[i + 1]) ? 0 : 1;
}
}
if (tmpLength > maxLength) {
maxLength = tmpLength;
}
// final Answer is number of elements (which is maxLength+1)
System.out.println("MaxSubLen:" + (maxLength + 1));
}
}
The idea I got to solve this problem was to use the previous comparation, if they are opposite I continue generating the sub-sequence. Ones I get a subsequence I can skyp lenght-1, I need to start lenght -1 because that can be the starting of the next valid subsequence.
public int[] FindLongestAlternatingSequence(int[] a)
{
int maxStart = -1;
int maxEnd = -1;
if (a == null || a.Length < 2)
return new int[0];
int i = 0;
int length = a.Length - 1;
while (i < length)
{
bool equals = a[i] == a[i + 1];
bool curr = a[i] > a[i + 1];
bool prev = !curr;
int start = i;
int j = i;
while (j < length && !equals && curr == !prev)
{
j += 2;
if (j >= length)
break;
prev = curr;
equals = a[j] == a[j + 1];
curr = a[j] > a[j + 1];
}
int end = (j <= a.Length) ? j - 1 : j - 3;
int l = end - start;
if (l > maxEnd - maxStart)
{
maxStart = start;
maxEnd = end;
}
if (l <= 0)
i++;
else
i = end;
}
if (maxStart == -1)
return new int[0];
int n = maxEnd - maxStart + 1;
int[] result = new int[n];
for (int j = 0; j < n; j++)
result[j] = a[j + maxStart];
return result;
}
private void test_Click(object sender, EventArgs e)
{
var a = new int[] { 2, 4, 5, 7, 3, 1, 5, 8, 8, 8, 5, 4, 3, 4, 5, 2, 1, 5, 4, 7, 7 };
var result = FindLongestAlternatingSequence(a);
for (int i = 0; i < result.Length; i+=2)
Console.Write("[" + result[i] + ", " + result[i + 1] + "] - ");
Console.WriteLine();
}
A typical top-down approach would be to maintain a direction (up/down) in each recursive call to the function that's calculating the longest subsequence.
def longestAlternatingSub(soFar: Vector[Int],
direction: Option[Boolean],
s: Vector[Int]): Vector[Int] = {
if (s.isEmpty)
soFar
else {
val firstVal = s.head
if (direction.isEmpty) {
// start with first increasing
val long1 = longestAlternatingSub(soFar :+ firstVal, Some(true), s.tail)
val long2 = longestAlternatingSub(soFar :+ firstVal, Some(false), s.tail)
val long3 = longestAlternatingSub(soFar, None, s.tail)
List(long1, long2, long3).sortBy(_.length).last
}
else if (direction.exists(_ == true) && soFar.lastOption.exists(_ < firstVal)){
val long1 = longestAlternatingSub(soFar :+ firstVal, Some(false), s.tail)
val long2 = longestAlternatingSub(soFar, Some(true), s.tail)
List(long1, long2).sortBy(_.length).last
}
else if (direction.exists(_ == false) && soFar.lastOption.exists(_ > firstVal)) {
val long1 = longestAlternatingSub(soFar :+ firstVal, Some(true), s.tail)
val long2 = longestAlternatingSub(soFar, Some(false), s.tail)
List(long1, long2).sortBy(_.length).last
}
else
Vector.empty
}
}
This can be easily memoized, or made a bottom-up dynamic programming solution to save space.
Java Code with test cases:
public class LongestAlternatingSubsequence
{
private int array[];
LongestAlternatingSubsequence(int[] array)
{
this.array = array;
}
public void setArray(int[] array)
{
this.array = array;
}
int findLongestAlternatingSubSequence()
{
//Null and length checks
if (this.array == null)
{
return -1;
}
int length = this.array.length;
if (length == 0)
{
return -1;
}
//Core logic starts
int from=-1, to=-1;
int tempFrom=-1, tempTo=-1;
for (int i=1; i<length; i++)
{
tempTo=i;
if (i%2 == 1)
{
if (!(this.array[i-1] > this.array[i]) && tempTo-tempFrom > to-from)
{
to=tempTo;
from=tempFrom;
tempFrom=i-1;
}
}
else
{
if (!(this.array[i] > this.array[i-1]) && tempTo-tempFrom > to-from)
{
to=tempTo;
from=tempFrom;
tempFrom=i-1;
}
}
}
System.out.println("To: " +to+"From: "+from);
return to - from;
}
}
//Test Case:
import org.junit.Test;
import java.util.Arrays;
import static org.junit.Assert.*;
public class LongestAlternatingSubsequenceTest
{
@Test
public void findLongestAlternatingSubSequence() throws Exception
{
LongestAlternatingSubsequence subsequence = new LongestAlternatingSubsequence(null);
assertEquals(-1, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45});
assertEquals(10, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 11});
assertEquals(10, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 52, 60, 55, 70, 68, 80, 76, 75, 12, 11});
assertEquals(8, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 52, 60, 55, 54, 68, 80, 76, 75, 12, 11});
assertEquals(8, subsequence.findLongestAlternatingSubSequence());
}
}
public class LongestAlternatingSubsequence{
public static int[] getLongestAlternatingSequence(int[] array){
if(array==null || array.length ==1){
return array;
}
int lowIndex,highIndex;
int tempLow=0, tempHigh;
boolean peak=false;
boolean sequenceEnd=false;
if(array[0] >array[1]){
peak = true;
}
for(int i=1; i<array.length;i++){
if(peak){
if(array[i] <array[i-1]){
tempHigh=i;
peak= false;
}
else{
sequenceEnd=true;
}
}
else{
if(array[i] > array[i-1]){
tempHigh=i;
peak=true;
}
else{
sequenceEnd=true;
}
}
if(sequenceEnd){
if(tempHigh-tempLow >= highIndex-lowIndex){
lowIndex= tempLow;
highIndex = tempHigh;
}
tempLow= i;
tempHigh=i;
sequenceEnd=false;
}
}
arraycopy(array, lowIndex, longestaltseq, 0, highIndex-lowIndex);
return longestaltseq;
}
}
public static void LIS_bottom_up(int[] array,int length)
{
int[] array2 = {4,6,7,3,9,5,7,0,-1,10};
int max = Integer.MIN_VALUE;
int[] tmparray_increase = new int[length+1];
int[] tmparray_decrease = new int[length+1];
for(int i=0;i<=length;i++)
{
tmparray_increase[i]=1;
tmparray_decrease[i]=1;
for(int j=0;j<=i;j++)
{
if(array[j]<array[i])
{
tmparray_increase[i]=Math.max(tmparray_increase[i], tmparray_decrease[j]+1);
}
if(array[j]>array[i])
{
tmparray_decrease[i]=Math.max(tmparray_decrease[i], tmparray_increase[j]+1);
}
}
max = Math.max(max, Math.max(tmparray_increase[i],tmparray_decrease[i]));
}
for(int i=0;i<=length;i++)
{
System.out.print(tmparray_increase[i]+"\t");
}
System.out.print("\n");
for(int i=0;i<=length;i++)
{
System.out.print(tmparray_decrease[i]+"\t");
}
System.out.println("Max = "+max);
}
List<startEnd> sequences = new ArrayList<startEnd>();
boolean sequenceRunning = false;
int start = -1, end = 0;
int next=0;//0=>, 1=<
Integer a[] = { 6, 7, 1, 9, 4, 3, 2, 5 };// new Integer[10];
Integer b[]= new Integer[a.length - 1];
// reArrangeOrder(a);
for (int i = 0; i < a.length - 1; i++) {
b[i] = a[i+1] - a[i];
}
for (int i = 0; i < b.length; i++) {
if(b[i]<0){
b[i] = 0;
}
else{
b[i] = 1;
}
}
//previous code subtract a[i] from a[i+1] after which if a[i] is >0 then puts 1 else 0
printArray(b);
for (int i = 0; i < b.length; i++) {
if((i+1) < b.length && b[i] != b[i+1])
{
//continue the sequence
if(start == -1){
start = i;
}
}
else{
end =i+1;
if(start !=-1)
{
sequences.add(new startEnd(start, end));
}
start = -1;
}
}
//previous code tells the start and end index of alternating 1,0
printList(sequences);//this method prints the start and end index of the subsequences which justify the order><><><>
List<startEnd> sequences = new ArrayList<startEnd>();
boolean sequenceRunning = false;
int start = -1, end = 0;
int next=0;//0=>, 1=<
Integer a[] = { 6, 7, 1, 9, 4, 3, 2, 5 };// new Integer[10];
Integer b[]= new Integer[a.length - 1];
// reArrangeOrder(a);
for (int i = 0; i < a.length - 1; i++) {
b[i] = a[i+1] - a[i];
}
for (int i = 0; i < b.length; i++) {
if(b[i]<0){
b[i] = 0;
}
else{
b[i] = 1;
}
}
//previous code subtract a[i] from a[i+1] after which if a[i] is >0 then puts 1 else 0
printArray(b);
for (int i = 0; i < b.length; i++) {
if((i+1) < b.length && b[i] != b[i+1])
{
//continue the sequence
if(start == -1){
start = i;
}
}
else{
end =i+1;
if(start !=-1)
{
sequences.add(new startEnd(start, end));
}
start = -1;
}
}
//previous code tells the start and end index of alternating 1,0
printList(sequences);//this method prints the start and end index of the subsequences which justify the order><><><>
using System;
using System.Collections.Generic;
using System.Linq;
namespace Ed1
{
public class Program
{
public static void Main(string[] args)
{
List<int> values = new List<int>(args.Length);
foreach (string arg in args)
values.Add(int.Parse(arg));
int resultPosition = 0;
int resultLength = 0;
FindSequence(values, ref resultPosition, ref resultLength);
string result = "";
for (int i = resultPosition; i < resultPosition + resultLength; i++)
result = result + values[i] + " ";
Console.WriteLine(result);
}
public static void FindSequence(IList<int> values, ref int resultPosition, ref int resultLength)
{
resultLength = 0;
resultPosition = 0;
int position = 0;
while (position < values.Count())
{
int length = SequenceLength(values, position);
if (length > resultLength)
{
resultLength = length;
resultPosition = position;
}
position = position + length;
}
}
static int SequenceLength(IList<int> values, int start)
{
if (start < 0 || start >= values.Count())
throw new IndexOutOfRangeException("start");
if (start == values.Count() - 1)
return 1;
if (values[start] == values[start + 1])
return 1;
int i = start + 2;
while
(
i < values.Count() &&
(
values[i - 2] < values[i - 1] &&
values[i] < values[i - 1]
||
values[i - 2] > values[i - 1] &&
values[i] > values[i - 1]
)
)
i = i + 1;
return i - start;
}
}
}
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Ed1;
namespace Ed1UnitTest
{
[TestClass]
public class UnitTest
{
[TestMethod]
public void TestMethod1()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = {1};
Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);
Assert.AreEqual(resultPosition, 0);
Assert.AreEqual(resultLength, 1);
}
[TestMethod]
public void TestMethod2()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = { };
Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);
Assert.AreEqual(resultPosition, 0);
Assert.AreEqual(resultLength, 0);
}
[TestMethod]
public void TestMethod3()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = {0, 2 };
Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);
Assert.AreEqual(resultPosition, 0);
Assert.AreEqual(resultLength, 2);
}
[TestMethod]
public void TestMethod4()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = {-1, -1, 4, 2, 5, 3, 2, 5, 0};
Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);
Assert.AreEqual(resultPosition, 1);
Assert.AreEqual(resultLength, 5);
}
[TestMethod]
public void TestMethod5()
{
int resultPosition = 0;
int resultLength = 0;
int[] values = { -1, -1, 4, 2, 5, 3 };
Ed1.Program.FindSequence(values, ref resultPosition, ref resultLength);
Assert.AreEqual(resultPosition, 1);
Assert.AreEqual(resultLength, 5);
}
}
}
Here'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);
}
enum direction {
Up, Down, NoChange
};
size_t LongestAlternatingSubSequence(const vector<long>& data, vector<long>& result)
{
map<size_t, size_t> sequences;
direction direction = NoChange, flag = NoChange;
size_t count = 0, start = 0, index = 0;
if (data.size() > 1) {
for (vector<long>::const_iterator it = data.begin() + 1; it != data.end(); it++, index++) {
flag = *it > *(it - 1) ? Up : *it < *(it -1 ) ? Down : NoChange;
if (flag != direction) {
count++;
direction = flag;
} else {
direction = NoChange;
if (sequences.find(index - start) == sequences.end())
sequences.emplace(index - start, start);
start = index;
}
}
}
if (sequences.size() > 0)
for (size_t i = 0; i <= sequences.rbegin()->first; i++)
result.push_back(data[i + sequences.rbegin()->second]);
return result.size();
}
A lot of the other answers were very dense and lacking comments. Additionally, the solutions were brittle to maintenance or changing requirements. Here is a solution that might be found in a real application.
import java.util.*;
import java.lang.*;
import java.io.*;
class LongestAlternatingSubsequence
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] numbers = new int[]{1,2,3,2,5,8};
int[] longestSubsequence = findLongest(numbers);
System.out.println(Arrays.toString(longestSubsequence));
}
private static int[] findLongest(int[] numbers) {
// For empty or single elemnt lists, the whoe list is the answer
if (numbers.length < 2) {
return numbers;
}
// Track the lonst sequence seen so far, and the list of sequences
// still under consideration
Sequence longest = null;
List<Sequence> activeSequences = new ArrayList();
for (int i=0;i<numbers.length;i++) {
int current=numbers[i];
// Track the sequences that survive the newly seen number
List<Sequence> nextSequences = new ArrayList();
// For every active sequence, evaluate whether the newly seen
// number breaks or continues the chain
for (Sequence sequence : activeSequences) {
Sequence nextSequence = sequence.considerNext(current);
if (nextSequence != null) {
// If the chain continues, then add it to the collection
// of sequences to keep watching
nextSequences.add(nextSequence);
} else {
// If the chain is broken, then check to see if it was a
// new longest chain seen
if (longest == null || longest.length < sequence.length) {
longest = sequence;
}
}
}
// For every element in the list, a new sequence is started with
// the possibility of the next number being smaller or larger
nextSequences.add(new Sequence(i, 1, current, true));
nextSequences.add(new Sequence(i, 1, current, false));
// Keep only the sequences that are unbroken for the next
// loop iteration
activeSequences = nextSequences;
}
// After all elements in the list are considered, evaluate all active
// sequences to see if the longest is in the list
for (Sequence sequence : activeSequences) {
if (longest == null || longest.length < sequence.length) {
longest = sequence;
}
}
// Using the longest sequence seen, find the substring of elements that
// represents the longest alternating substring
return Arrays.copyOfRange(numbers, longest.startIndex, longest.startIndex+longest.length);
}
}
/**
* Track an active sequence and provide a method of evaluating a new element to
* see if the sequence has been broken or should be continued. In a performance
* critical application, this logic could be rolled into the loops above, but
* in a practical application keeping is separate allows each substitution of
* new subsequence rules.
*/
class Sequence {
int length;
int startIndex;
int last;
boolean expectLarger;
public Sequence(int startIndex, int length, int last, boolean expectLarger) {
this.length = length;
this.startIndex = startIndex;
this.last = last;
this.expectLarger = expectLarger;
}
public Sequence considerNext(int next) {
if (this.expectLarger) {
if (next > this.last) {
return new Sequence(this.startIndex, this.length+1, next, !this.expectLarger);
} else {
return null;
}
} else {
if (next < this.last) {
return new Sequence(this.startIndex, this.length+1, next, !this.expectLarger);
} else {
return null;
}
}
}
}
void getLongestAlternatingSequence(const vector<int>& a, int& start, int& end) {
start=end=-1; // init output with -1
if (a.size()==0 || a.size()==1) {
return; // error handling
}
for (int _start=0, _end=0; _start<a.size()-1; ++_start) {
if(a[_start]==a[_start+1]){ // skip adjacent duplicates
continue;
}
_end =_start+1; // start of candidate sequence
while( ( (_end+1) < a.size() ) && (a[_end]>a[_end-1]) ? (a[_end+1]<a[_end]) : (a[_end+1]>a[_end]) {
_end++; // continue accumulating current alternating sequence
}
if ((end-start) < (_end-_start)) { // update outputs if longer sequence found
start=_start;
end=_end;
}
_start=_end; // reset start position of next candidate alt sequence
}
}
void getLongestAlternatingSequence(const vector<int>& a, int& start, int& end) {
start=end=-1; // init output with -1
if (a.size()==0 || a.size()==1) {
return; // error handling
}
for (int _start=0, _end=0; _start<a.size()-1; ++_start) {
if(a[_start]==a[_start+1]){ // skip adjacent duplicates
continue;
}
_end =_start+1; // start of candidate sequence
while( ( (_end+1) < a.size() ) && (a[_end]>a[_end-1]) ? (a[_end+1]<a[_end]) : (a[_end+1]>a[_end]) {
_end++; // continue accumulating current alternating sequence
}
if ((end-start) < (_end-_start)) { // update outputs if longer sequence found
start=_start;
end=_end;
}
_start=_end; // reset start position of next candidate alt sequence
}
}
int longestIncreasingSeq(int a[], int aSize)
{
int* increasingSeq = new int[aSize];
int* decreasingSeq = new int[aSize];
for (int index = 0; index < aSize; index++)
{
increasingSeq[index] = 0;
decreasingSeq[index] = 0;
}
decreasingSeq[0] = -1;
for (int index = 1; index < aSize; index++)
{
if (a[index] > a[index -1])
{
increasingSeq[index ] = decreasingSeq[index - 1]+ 1;
}
else if (a[index] < a[index - 1])
{
decreasingSeq[index] = increasingSeq[index - 1] + 1;
}
cout << increasingSeq[index] << ":" << decreasingSeq[index]<<endl;
}
int maxIncreasingSeq = 0;
for (int index = 0; index < aSize; index++)
{
if (maxIncreasingSeq < increasingSeq[index])
{
maxIncreasingSeq = increasingSeq[index];
}
if (maxIncreasingSeq < decreasingSeq[index])
{
maxIncreasingSeq = decreasingSeq[index];
}
}
return maxIncreasingSeq;
}
int longestIncreasingSeq(int a[], int aSize)
{
int* increasingSeq = new int[aSize];
int* decreasingSeq = new int[aSize];
for (int index = 0; index < aSize; index++)
{
increasingSeq[index] = 0;
decreasingSeq[index] = 0;
}
decreasingSeq[0] = -1;
for (int index = 1; index < aSize; index++)
{
if (a[index] > a[index -1])
{
increasingSeq[index ] = decreasingSeq[index - 1]+ 1;
}
else if (a[index] < a[index - 1])
{
decreasingSeq[index] = increasingSeq[index - 1] + 1;
}
cout << increasingSeq[index] << ":" << decreasingSeq[index]<<endl;
}
int maxIncreasingSeq = 0;
for (int index = 0; index < aSize; index++)
{
if (maxIncreasingSeq < increasingSeq[index])
{
maxIncreasingSeq = increasingSeq[index];
}
if (maxIncreasingSeq < decreasingSeq[index])
{
maxIncreasingSeq = decreasingSeq[index];
}
}
return maxIncreasingSeq;
}
Solution in C++
#include <iostream>
#include <vector>
typedef std::vector<int> vec_t;
int
findMax(vec_t& aVec) {
int lMax = 0;
for(int i = 0; i < aVec.size(); ++i)
if (aVec[i] > lMax) lMax = aVec[i];
return lMax;
}
void
print(vec_t& aVec) {
for(auto& a : aVec)
std::cout << a << ' ';
std::cout << std::endl;
}
int
maxZigZag(vec_t& aVec) {
vec_t pos(aVec.size(),1);
vec_t neg(aVec.size(),1);
for(int i = 1; i < aVec.size(); ++i) {
for(int j = 0; j <= i-1; ++j) {
if(aVec[i] - aVec[j] > 0) {
pos[i] = std::max(neg[j]+1, pos[i]);
} else if (aVec[i] - aVec[j] < 0) {
neg[i] = std::max(pos[j]+1, neg[i]);
}
}
}
int l1 = findMax(pos);
int l2 = findMax(neg);
/* print(pos); print(neg); */
return std::max(l1, l2);
}
My solution has O(n) complexity - it goes through the array only once, and what is does is keep track of 2 elements before the current one, and check on the sign of the difference between the current element and the previous multiplied by the difference between the previous and the pre-previous element. The result of this multiplication needs to be negative for the sequence of 3 elements currently assessed (crt elem, previous, pre-previous) to be alternative. And then it reports the maximum length.
# The code assumes that the array has a length >= 2
def find_largest_alt_seq(array):
max = 0
crt_len = 2
prev = array[1]
prev_prev = array[0]
for elem in array[2:]:
if (elem - prev) * (prev - prev_prev) < 0:
crt_len += 1
else:
if crt_len > 0:
if max < crt_len:
max = crt_len
crt_len = 0
prev_prev = prev
prev = elem
if crt_len > 0 and max < crt_len:
max = crt_len
return max
def find_largest_alt_seq(array):
max = 0
crt_len = 2
prev = array[1]
prev_prev = array[0]
for elem in array[2:]:
if (elem - prev) * (prev - prev_prev) < 0:
crt_len += 1
else:
if crt_len > 0:
if max < crt_len:
max = crt_len
crt_len = 0
prev_prev = prev
prev = elem
if crt_len > 0 and max < crt_len:
max = crt_len
return max
Zig Zag subsequence. Variation of increasing subsequence.
- xeq March 19, 2016