给定一个数组 = {1 2 3 3 2 4 6 7}
最长递增子数组是 2 4 6 7。需要注意的是，这与最长递增子序列并不相同，因为值必须是连续的。
是否有 O(n) 的解决方案？
10个回答
15
你可以使用动态规划。
伪代码：
伪代码：
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
- Jun HU
2
但由于dp数组需要O(N)的空间，因此需要更多的空间。 - v.shashenko
dp数组可以改为两个变量（当前和前一个），使空间复杂度为O(1)。 - user274595
4
1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1 2 3 | 1 | 1 2 3 4 <- Length of runs
从左到右遍历数组。记录当前连续序列的长度。
当连续序列结束时，将其与迄今为止的最佳连续序列进行比较，其中存储了长度和结束位置。如果刚刚结束的序列更好，更新最佳连续序列数据。
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
由于您只遍历一次数组，每次仅访问一个元素和最佳运行数据，因此每个元素的时间是恒定的。因此，该算法的运行时间为O(n)。
- phant0m
4
是的，你可以用o(n)的时间复杂度找到最长的子数组。从开头开始，记录当前序列和最长的序列。每一步，如果元素比前一个大，则增加当前序列的长度。如果当前序列比最长序列长，则更新最长序列。如果当前元素比前一个小，则重置计数器。最后你会得到最长的序列。
- Z.D.
3
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);`
时间复杂度：O(n) 空间复杂度：O(1)
- sarjit07
2
您应该能够按照如下线性时间解决这个问题。每次保留以下各点信息：
希望这可以帮助您！
- 到目前为止已看到的最长递增子数组的长度/起始点
- 您所见过的数组中的最后一个元素（如果尚未看到任何内容，则为哨兵值）
- 以当前值结尾的最长递增子数组的长度。
- 如果前一个值是哨兵值：
- 将前一个值设置为当前值。
- 将当前长度设置为1。
- 否则，如果前一个值小于当前值：
- 将前一个值设置为当前值。
- 增加当前子数组的长度。
- 否则，如果前一个值大于当前值：
- 将前一个值设置为当前值。
- 将当前长度设置为1。
- 无论上述条件是否成立，如果当前长度大于找到的最大长度：
- 将找到的最大长度设置为当前长度。
- 记录到目前为止发现的序列的开头（它是当前长度减去该序列中第一个元素的位置）。
希望这可以帮助您！
- templatetypedef
1
Jun HU的回答是正确的，但我认为我们不需要维护一个占用O(n)空间的数组。相反，我们可以跟踪当前子数组的大小，类似于
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;
}
}
这种方法有效是因为数组已排序，如果当前元素不高于前一个元素，则当前子数组不再按递增顺序排列，因此我们不再关心其大小。通过这种方式，我们实现了恒定的空间复杂度，同时保持线性时间复杂度。
- jramell
0
这不是动态规划的解决方案，但我尝试了一些场景，看起来可以正常工作。也许对你来说是一个很好的起点。
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;
}
- Asad Durrani
0
这将为您提供范围（起始和结束索引）。
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;
}
}
- andres.santana
0
一个Java的O(n)实现，同时也是通用的，可以用于任何事情！
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);
}
}
- PoweredByRice
0
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]
- bainikolaus
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接