给定一个数组 = {1 2 3 3 2 4 6 7}
最长递增子数组是 2 4 6 7。请注意，这与最长递增子序列不同，因为这些值必须是连续的。
这个问题是否有任何 O(n) 解决方案？
问问题
12953 次
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
于 2013-01-24T02:30:19.323 回答
4
是的，你可以用 o(n) 找到最长的子数组。从头开始跟踪当前序列和最长序列。在元素的每一步都比前一个更大的时候增加当前序列的长度。如果当前序列比最长序列长，则更新最长序列。如果当前元素小于前一个元素，则重置计数器。最后，您将获得最长的序列。
于 2013-01-24T00:53:18.307 回答
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).
于 2013-01-24T10:37:15.050 回答
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)
于 2016-01-13T18:21:34.413 回答
2
您应该能够在线性时间内解决这个问题，如下所示。保持在每个点
- 到目前为止看到的最长递增子数组的长度/起点，
- 您看到的数组中的最后一个元素（如果您还没有看到任何东西，则为哨兵值），并且
- 以当前值结尾的最长递增子数组的长度。
然后，您可以一次循环遍历数组，并对每个值执行以下操作：
- 如果前一个值是哨兵：
- 将先前的值设置为当前值。
- 将当前长度设置为 1。
- 否则，如果先前的值小于当前值：
- 将先前的值设置为当前值。
- 增加当前子数组的长度。
- 否则，如果前一个值大于当前值：
- 将前一个值设置为当前值
- 将当前长度设置为 1。
- 与上述无关，如果当前长度大于找到的最大长度：
- 将找到的最大长度设置为当前长度。
- 记录到目前为止您发现的序列的开始（它是当前长度减去该序列中第一个元素的位置）。
这确实 O(1) 工作 O(n) 次，因此整个解决方案在 O(n) 时间内运行。
希望这可以帮助！
于 2013-01-24T00:48:20.397 回答
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;
}
}
这是有效的，因为在对数组进行排序时，如果当前元素不高于前一个元素，则当前子数组不再按递增顺序排列，因此我们不再关心它的大小。这样，我们实现了恒定的空间复杂度，同时保持了线性时间复杂度。
于 2017-08-13T20:32:33.133 回答
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]
于 2013-11-18T16:13:31.263 回答
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);
}
}
于 2014-02-02T03:50:46.467 回答
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;
}
}
于 2015-05-15T16:01:13.533 回答
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;
}
于 2016-04-16T15:12:25.433 回答