Pengaturcaraan Dinamik Hari LeetCode Bahagian 10

    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>


<div class="code" style="position:relative; padding:0px; margin:0px;"><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!