Pengaturcaraan Dinamik Hari LeetCode Bahagian 10

300. Susulan Bertambah Terpanjang

Memandangkan nombor tatasusunan integer, kembalikan panjang terpanjang yang semakin meningkat dengan ketat
seterusnya
.

Contoh 1:

Input: nombor = [10,9,2,5,3,7,101,18]
Keluaran: 4
Penjelasan: Susulan peningkatan terpanjang ialah [2,3,7,101], oleh itu panjangnya ialah 4.
Contoh 2:

Input: nombor = [0,1,0,3,2,3]
Keluaran: 4
Contoh 3:

Input: nombor = [7,7,7,7,7,7,7]
Keluaran: 1

Kekangan:

1 <= nums.length <= 2500
-10^4 <= angka[i] <= 10^4

Susulan: Bolehkah anda menghasilkan algoritma yang berjalan dalam kerumitan masa O(n log(n))?
Halaman Asal

Kod yang salah

    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);
    }


</p>
<h2>
  
  
  Betulkan pepijat
</h2>


<pre class="brush:php;toolbar:false">

Belajar Daripada peta pokok orang lain

    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. Susulan Peningkatan Berterusan Terpanjang

Memandangkan tatasusunan nombor integer yang tidak diisih, kembalikan panjang jujukan peningkatan berterusan terpanjang (iaitu subarray). Susulan mesti meningkat dengan ketat.

Jujukan meningkat berterusan ditakrifkan oleh dua indeks l dan r (l < r) supaya ia adalah [nums[l], nums[l + 1], ..., nums[r - 1], nums [r]] dan bagi setiap l <= i < r, nombor[i] < nombor[i + 1].

Contoh 1:

Input: nombor = [1,3,5,4,7]
Keluaran: 3
Penjelasan: Susulan peningkatan berterusan terpanjang ialah [1,3,5] dengan panjang 3.
Walaupun [1,3,5,7] ialah urutan yang semakin meningkat, ia tidak berterusan kerana unsur 5 dan 7 dipisahkan oleh unsur
4.
Contoh 2:

Input: nombor = [2,2,2,2,2]
Keluaran: 1
Penjelasan: Susulan peningkatan berterusan terpanjang ialah [2] dengan panjang 1. Ambil perhatian bahawa ia mestilah betul-betul
semakin meningkat.

Kekangan:

1 <= nums.length <= 10^4
-10^9 <= angka[i] <= 10^9
Halaman Asal

Algoritma tamak

    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);
    }

Pengaturcaraan Dinamik

Berbeza daripada soalan sebelumnya, dalam soalan ini kita hanya boleh mempertimbangkan urutan yang terus meningkat, yang memudahkan proses.

Atas ialah kandungan terperinci Pengaturcaraan Dinamik Hari LeetCode Bahagian 10. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!