Reputation: 3177
Longest subarray that has elements in increasing order?
Given an array = {1 2 3 3 2 4 6 7}
The longest increasing subarray is 2 4 6 7. Note that this isn't the same as the longest increasing subsequence, since the values have to be contiguous.
Is there any O(n) solution for this problem?
Upvotes: 3
Views: 15598
Answers (10)
Reputation: 9
Jun HU's answer is correct, but I don't think we need to maintain an array that would take up O(n) space. We can instead track the size of the current subarray, something like
int maxSize, currentSize = 1;
for (int i = 1; i < array.size(); i++) {
if (array[i] > array[i-1]) {
currentSize++;
maxSize = max(currentSize, maxSize);
} else {
currentSize = 1;
}
}
This works because, as the array is sorted, if the current element is not higher than the previous one, the current subarray is no longer in increasing order and thus we no longer care about its size. This way, we achieve constant space complexity while maintaining linear time complexity.
Upvotes: 1
Reputation: 2237
This is not dynamic programming solution but I just tried it for some scenarios and it looks to work okay with those. May be a good starting point for you
public static int MaxSlice(int[] A)
{
//100,40,45,50,55,60, 30,20,40,25,28,30
int maxstartIndex = 0;
int MaxAscendingCount = 0;
int thisStartIndex = 0;
int thisAscendingCount = 0;
bool reset = false;
bool wasLastAscending = false;
for (int i = 0; i < A.Length-1; i++ )
{
if (A[i + 1] > A[i])
{
if(!wasLastAscending)
thisStartIndex = i;
thisAscendingCount++;
wasLastAscending = true;
}
else
{
reset = true;
wasLastAscending = false;
}
if (reset && thisAscendingCount > MaxAscendingCount)
{
MaxAscendingCount = thisAscendingCount;
maxstartIndex = thisStartIndex;
reset = false;
thisAscendingCount = 0;
}
}
MaxAscendingCount = thisAscendingCount;
maxstartIndex = thisStartIndex;
return maxstartIndex;
}
Upvotes: 0
Reputation: 10769
int flag = 0;
int maxSubarray =0;
int maxStart=0,maxEnd=0,start=0,end=0;
for(int i=1;i<n;i++){
if(a[i-1]<a[i]){
if(flag!=1){
start = i-1;
flag=1;
}
if(i == n-1){
end = n-1;
}
}
else{
if(flag==1 ){
end = i-1;
flag =0;
}
}
if(maxSubarray < end - start){
maxSubarray = end - start;
maxStart = start;
maxEnd = end;
}
}
System.out.println(maxSubarray);
System.out.println("Starting index = "+maxStart+" Ending index = "+maxEnd);`
`
Time Complexity : O(n) Space Complexity: O(1)
Upvotes: 3
Reputation: 661
This will give you the Range(start and end index).
public static Range getLargest(int[] array) {
int max = 1;
int start = 0;
int aux = 0;
int count = 1;
for (int i = 1; i < array.length; i++) {
if (array[i] > array[i - 1]) {
count++;
} else {
aux = i;
count = 1;
}
if (count > max) {
max = count;
start = aux;
}
}
return new Range(start, start + max - 1);
}
public static class Range {
public final int start;
public final int end;
public Range(int start, int end) {
this.start = start;
this.end = end;
}
}
Upvotes: 0
Reputation: 2509
An O(n) implementation in Java, also generic so can be used for anything!
import java.util.Arrays;
public class LongestIncreasing {
private static class PairHolder<T> {
int start = -1;
int end = -1;
int weight = -1;
PairHolder(int start, int end) {
this.start = start;
this.end = end;
this.weight = start == -1 ? -1 : end-start+1;
}
String getSubArray(T[] arr) {
return Arrays.toString(Arrays.copyOfRange(arr, start, end+1));
}
@Override
public String toString() {
return "[" + start + ", " + end + ", weight: " + weight + "]";
}
}
public static <T extends Comparable<? super T>> void getContiguousChain(T[] chain) {
int start = -1, end = -1;
PairHolder<T> longest = new PairHolder<T>(-1, -1);
for (int i = 0; i < chain.length - 1; i++) {
if (start == -1) {
start = i;
end = i;
}
if (chain[i+1].compareTo(chain[i]) == -1 || chain[i+1].compareTo(chain[i]) == 0) {
if (end-start+1 > longest.weight) {
longest = new PairHolder<T>(start, end);
}
start = -1; end = -1;
continue;
}
end = i+1;
}
if (end-start+1 > longest.weight) { //corner case where last element of chain is also end of array
longest = new PairHolder<T>(start, end);
}
System.out.println(longest.getSubArray(chain));
}
public static void main(String[] args) {
Integer[] arr = {2, 3, 3, 4, 5, 6, 2, 9, 10, 12, 14, 13};
getContiguousChain(arr);
}
}
Upvotes: 0
Reputation: 141
def lis(a):
m = 0
c = 1
index = 0
for i in xrange(1, len(a)):
x = a[i]
if x > a[i - 1]:
c += 1
else:
if c > m:
m = c
index = i
c = 1
if c > m:
m = c
index = i
return a[i - m + 1: i + 1]
Upvotes: 0
Reputation: 3314
You can just use dynamic programming.
Pseudo code:
def DP(a[]):
dp[1] = 1
for i = 2 to n:
if a[i] > a[i - 1]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = 1
Upvotes: 15
Reputation: 16905
1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1 2 3 | 1 | 1 2 3 4 <- Length of runs
Traverse the array from left to right. Keep track of how long the current run is.
When the run ends, compare it to the best run so far, for which you store the length and the position where it ended. If the run that just ended is better, update the best-run data.
1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1 2 3 | 1 | 1 2
^
Longest run,
ending at index 2
1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1 2 3 | 1 | 1 2 3 4
^ ^
Longest run, Current run ends
ending at index 2 Better than last longest run, update
Since you only traverse the array once only accessing one element at a time and additionally the best-run data, you do constant time per element. Hence, the algorithm runs in O(n).
Upvotes: 5
Reputation: 12837
yes, you can find the longest subarray with o(n). starting from the beginning keep track of the current sequence and the longest sequence. on each step in the element is larger than the previous increase the length of the current sequence. if the current sequence is longer than the longest sequence, update the longest sequence. if the current element is smaller than the previous, reset the counter. at the end you'll have the longest sequence.
Upvotes: 4
Reputation: 373152
You should be able to solve this in linear time as follows. Maintain at each point
- The length / starting point of the longest increasing subarray seen so far,
- The last element in the array that you have seen (or a sentinel value if you haven't seen anything yet), and
- The length of the longest increasing subarray ending at the current value.
You can then loop over the array in one pass and do the following for each value:
- If the previous value is the sentinel:
- Set the previous value to the current value.
- Set the current length to 1.
- Otherwise, if the previous value is less than the current value:
- Set the previous value to the current value.
- Increment the length of the current subarray.
- Otherwise, if the previous value is greater than the current value:
- Set the previous value to the current value
- Set the current length to 1.
- Independently of the above, if the current length is greater than the max length found:
- Set the max length found to the current length.
- Record the start of the sequence you've discovered so far (it's the current length minus the position of the first element in that sequence).
This does O(1) work O(n) times, so the overall solution runs in time O(n).
Hope this helps!
Upvotes: 2
Related Questions
- Length of maximum subarray such that 1st element is greater than last element
- Length of Longest Subarray with all same elements
- Find the length of longest increasing subsequence C++
- Longest increasing sequence in an array in C
- Find the length of the longest repeated subArray
- Find the longest subarray that contains a majority element
- Longest subarray whose elements form a continuous sequence
- Longest positive subarray
- How to find the longest set of consecutive increasing (ascending) elements in array?
- Longest Increasing Subsequence from each element