LeetCode Day 動的プログラミング パート 10

300. 最長の増加サブシーケンス

整数配列 nums を指定すると、厳密に増加する最長の長さを返します
後続
.

例 1:

入力: nums = [10,9,2,5,3,7,101,18]
出力: 4
説明: 最も長く増加する部分列は [2,3,7,101] であるため、長さは 4 です。
例 2:

入力: nums = [0,1,0,3,2,3]
出力: 4
例 3:

入力: nums = [7,7,7,7,7,7,7]
出力: 1

制約:

1 -10^4

フォローアップ: O(n log(n)) の時間計算量で実行されるアルゴリズムを思いつきませんか?
オリジナルページ

間違ったコード

    public int lengthOfLIS(int[] nums) {
        int start = nums[0];
        int pre = nums[0];
        int preMax = nums[0];
        int cnt = 1;
        int max = 1;

        for(int i=1; i<nums.length; i++){
            if(nums[i] < start){
                max = Math.max(max, cnt);
                start = nums[i];
                cnt = 1;
            } 
            else if(nums[i] > pre){
                cnt ++;
            }
            pre = nums[i];
            System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt);
        }
        return Math.max(max, cnt);
    }

バグを修正

他の人から学ぶツリーマップ

    public int lengthOfLIS(int[] nums) {


        TreeMap<Integer,Integer> map = new TreeMap<>();

        map.put(Integer.MIN_VALUE,0);

       for(int i: nums)
       {
           map.put(i,map.get(map.lowerKey(i))+1);
           while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i)) 
           {
            map.remove(map.higherKey(i));
           }
       }

       return map.get(map.lastKey());

    }

---

674. 最長連続増加サブシーケンス

ソートされていない整数 num の配列を指定すると、最長の連続増加サブシーケンス (つまり、部分配列) の長さを返します。後続シーケンスは厳密に増加している必要があります。

連続的に増加するサブシーケンスは、[nums[l], nums[l + 1], ..., nums[r - 1], nums のように、2 つのインデックス l と r (l < r) によって定義されます。 [r]] および各 l <= i < r、nums[i] <; nums[i + 1].

例 1:

入力: nums = [1,3,5,4,7]
出力: 3
説明: 最長の連続増加サブシーケンスは、長さが 3 の [1,3,5] です。
[1,3,5,7] は増加するサブシーケンスですが、要素 5 と 7 は要素
で区切られているため連続していません。 4.
例 2:

入力: nums = [2,2,2,2,2]
出力: 1
説明: 最長の連続増加サブシーケンスは、長さが 1 の [2] です。厳密に
である必要があることに注意してください。 増えています。

制約:

1 <= nums.length <= 10^4
-10^9 <= nums[i]
オリジナルページ

貪欲なアルゴリズム

    public int findLengthOfLCIS(int[] nums) {
        if(nums.length < 1){
            return 0;
        }
        int res = 1;
        int cnt = 1;
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i] > pre){
                cnt++;
            }else{
                res = Math.max(res, cnt);
                cnt = 1;
            }
            // System.out.println("cur: " + nums[i] + " pre:" + pre + " count:" + cnt);
            pre = nums[i];
        }
        return Math.max(res, cnt);
    }

動的プログラミング

前の質問とは異なり、この質問では継続的に増加するサブシーケンスのみを考慮できるため、プロセスが簡素化されます。

以上がLeetCode Day 動的プログラミング パート 10の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。