与えられた配列={12 3 3 2 4 6 7}
最長増加部分列は246 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
一度に 1 つの要素にアクセスするだけで配列を 1 回だけ走査し、さらに最適な実行データにアクセスするため、要素ごとに一定の時間を実行します。したがって、アルゴリズムは で実行され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 に設定します。
- そうでなく、前の値が現在の値より小さい場合:
- 以前の値を現在の値に設定します。
- 現在の部分配列の長さを増やします。
- それ以外の場合、以前の値が現在の値より大きい場合:
- 前の値を現在の値に設定する
- 現在の長さを 1 に設定します。
- 上記とは別に、現在の長さが見つかった最大長よりも大きい場合:
- 見つかった最大長を現在の長さに設定します。
- これまでに発見したシーケンスの開始を記録します (現在の長さからそのシーケンスの最初の要素の位置を引いたものです)。
これは O(1) を O(n) 回実行するため、全体のソリューションは O(n) の時間で実行されます。
お役に立てれば！
于 2013-01-24T00:48:20.397 に答える
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
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 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 に答える
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 に答える