The idea for the O(n) solution is to keep track of the start of the longest continuous increasing sequence and it's length. At each item, if it's bigger than the previous, then we have a sequence. If it's longer then the current maximum length, then we have a new longest increasing sequence, longer than the previous one.
void longestContinuousIncrSeq(int* a, int size) {
int maxstart = 0;
int max = 1;
int start = 0;
for (int i = 1; i < size; i++) {
if (a[i] > a[i - 1]) {
if (i - start + 1 > max) {
max = i - start + 1;
maxstart = start;
}
} else {
start = i;
}
}
cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;
for (int i = 0; i < max; i++) {
cout << a[maxstart + i] << " ";
}
cout << endl;
}
From EPI 6.6
static Pair<Integer, Integer> findLongestIncreasingSubarray(List<Integer> A) {
int maxLen = 1;
Pair<Integer, Integer> ans = new Pair<Integer, Integer>(0, 0);
int i = 0;
while (i < A.size()) {
// Checks backwardly and skip if A[j] >= A[j + 1].
boolean isSkippable = false;
for (int j = i + maxLen - 1; j >= i; --j) {
if (j + 1 >= A.size() || A.get(j) >= A.get(j + 1)) {
i = j + 1;
isSkippable = true;
break;
}
}
// Checks forwardly if it is not skippable.
if (isSkippable == false) {
i += maxLen - 1;
while (i + 1 < A.size() && A.get(i) < A.get(i + 1)) {
++i;
++maxLen;
}
ans = new Pair<Integer, Integer>(i - maxLen + 1, i);
}
}
return ans;
}
Read full article from World of BROCK: How to find the longest continuous increasing sequence: algorithms, puzzles, howto's and stuff... interview questions..etc
void longestContinuousIncrSeq(int* a, int size) {
int maxstart = 0;
int max = 1;
int start = 0;
for (int i = 1; i < size; i++) {
if (a[i] > a[i - 1]) {
if (i - start + 1 > max) {
max = i - start + 1;
maxstart = start;
}
} else {
start = i;
}
}
cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;
for (int i = 0; i < max; i++) {
cout << a[maxstart + i] << " ";
}
cout << endl;
}
From EPI 6.6
static Pair<Integer, Integer> findLongestIncreasingSubarray(List<Integer> A) {
int maxLen = 1;
Pair<Integer, Integer> ans = new Pair<Integer, Integer>(0, 0);
int i = 0;
while (i < A.size()) {
// Checks backwardly and skip if A[j] >= A[j + 1].
boolean isSkippable = false;
for (int j = i + maxLen - 1; j >= i; --j) {
if (j + 1 >= A.size() || A.get(j) >= A.get(j + 1)) {
i = j + 1;
isSkippable = true;
break;
}
}
// Checks forwardly if it is not skippable.
if (isSkippable == false) {
i += maxLen - 1;
while (i + 1 < A.size() && A.get(i) < A.get(i + 1)) {
++i;
++maxLen;
}
ans = new Pair<Integer, Integer>(i - maxLen + 1, i);
}
}
return ans;
}
Read full article from World of BROCK: How to find the longest continuous increasing sequence: algorithms, puzzles, howto's and stuff... interview questions..etc