LeetCode Day 동적 프로그래밍 10부

300. 가장 긴 증가 부분 수열

정수 배열 nums가 주어지면 가장 긴 길이를 엄격하게 증가시켜 반환합니다.
후속
.

예 1:

입력: 숫자 = [10,9,2,5,3,7,101,18]
출력: 4
설명: 가장 긴 증가 부분 수열은 [2,3,7,101]이므로 길이는 4입니다.
예시 2:

입력: 숫자 = [0,1,0,3,2,3]
출력: 4
예시 3:

입력: 숫자 = [7,7,7,7,7,7,7]
출력: 1

제약사항:

1 <= nums.length <= 2500
-10^4 <= 숫자[i] <= 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);
    }


</p>
<h2>
  
  
  버그 수정
</h2>


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

다른 사람으로부터 배우기

    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. 가장 긴 연속 증가 부분 수열

정렬되지 않은 정수 배열이 주어지면 가장 긴 연속 증가 부분 수열(즉, 하위 배열)의 길이를 반환합니다. 하위 수열은 엄격하게 증가해야 합니다.

연속 증가 부분 수열은 두 개의 인덱스 l과 r(l < r)로 정의되어 [nums[l], nums[l + 1], ..., nums[r - 1], nums가 됩니다. [r]] 그리고 각 l <= i < r, 숫자[i] < 숫자[i + 1].

예 1:

입력: 숫자 = [1,3,5,4,7]
출력: 3
설명: 가장 긴 연속 증가 부분 수열은 길이가 3인 [1,3,5]입니다.
[1,3,5,7]은 증가하는 부분수열이지만 요소 5와 7이 요소별로 분리되어 있으므로 연속적이지 않습니다
4.
예시 2:

입력: 숫자 = [2,2,2,2,2]
출력: 1
설명: 가장 긴 연속 증가 부분 수열은 길이가 1인 [2]입니다. 이는 엄격하게
이어야 합니다. 증가하고 있습니다.

제약사항:

1 <= nums.length <= 10^4
-10^9 <= 숫자[i] <= 10^9
원본페이지

그리디 알고리즘

    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 중국어 웹사이트의 기타 관련 기사를 참조하세요!