2 차원 영향 조건 정렬 문제 (정렬 + 최대 증가 서브 시퀀스 구하 기) js 실현

제목: 어떤 사람 이 몬스터 를 잡 아 많은 보물 을 얻 었 습 니 다. 그 는 보물 을 수집가 에 게 팔 려 고 합 니 다. 이 소장 가 는 습관 이 있 습 니 다. 바로 그 는 매번 에 이전 보물 보다 가치 가 낮은 보물 을 사지 않 습 니 다. 보물 의 가 치 를 평가 하 는 데 두 가지 인자 x 와 h 가 있 습 니 다. 한 가지 보물 의 x 와 h 가 다른 것 보다 높 아야 이 보물 이 다른 가치 보다 높다 고 말 할 수 있 습 니 다.보물 의 서열 을 정 해 팔 수 있 는 보물 의 최대 개 수 를 구하 자.
예 를 들 어 입력 [{x: 3, h: 2}, {x: 1, h: 3}, {x: 1, h: 1}, {x: 2, h: 2}], 출력 3
문제 풀이 방향: 우 리 는 먼저 보물 의 가치 에 대해 순 서 를 정 하고 최대 증가 서브 서열 을 찾 아야 한다 고 생각 합 니 다. 그러나 보물 의 가치 에 영향 을 주 는 요 소 는 두 가지 가 있 습 니 다. 따라서 우 리 는 먼저 영향 요 소 를 확정 한 다음 에 다른 하 나 를 고려 할 수 있 습 니 다. 먼저 우 리 는 x 에 따라 배열 에 대해 작은 것 에서 큰 것 으로 순 서 를 매 겨 서 얻 을 수 있 습 니 다. [{x: 1, h: 3}, {x: 1, h: 1}, {x: 2, h: 2},{x: 3, h: 2}] 영향 요 소 를 확정 한 후에 우 리 는 x 를 더 이상 고려 할 필요 가 없다. y 의 최 장 증가 서브 시퀀스 (여기 가 엄격 하지 않 은 지 주의 하 라) 에 따라 배열 이 필요 하 다. {3, 1, 2, 2} 의 최 장 비 엄격 한 증가 서브 시퀀스 는 {1, 2, 2} 이 므 로 결 과 는 3 이다. 그러나 이것 으로 는 부족 하 다. 예 를 들 어 [{x: 1, h: 2}, {x: 1, h: 1}, {x: 2, h: 3}, {x: 3, h: 3}{x: 4, h: 5}, {x: 4, h: 1}}, x 에 따라 다음 순 으로 나 누 었 다: [{x: 1, h: 2}, {x: 1, h: 1, h: 1}, {x: 2, h: 1}, {x: 2, 2, h: 3}, {x: 3, h: 4}, {x: 3, h: 3, h 3, 3, 3, h 3, 3, 3, 4, h: 4, 5}, {x: 4, 4, h: 1}, 1, 1, 1, 1, 1, 1, 3, 4, 3, 3, 3, 5, 5} 의 최 장 비 엄격 증가 자 서열 은 {1, 1, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5}, 5}, 5} 5. 팔 려 가 는 보물 은 [{x: 1, h: 1}, {x: 2, h: 1},{x: 2, h: 3}, {x: 3, h: 3}, {x: 4, h: 5}, 그러나 실제 결 과 는 6, 팔 수 있 는 보물 은 [{x: 1, h: 1, 1}, {x: 1, h: 1}, {x: 1, h: 2}, {x: 2, h: 3, {x: 3, h: 3, 3}, {x: 4, h: 5}, {x: 1, 1, 2, 3, h: 1, h: 1, h: 1, h: 1, h: 1, h: 1, h: 1, h: 1, h: 1, 1, 2, 3, 3, {x: 4, h: 5}}}, 5}, {x: 5}}}, 1, 1, 1, 1, 1, 1, 1, 1,, 5, 1}최 장 비 엄격 한 증가 서브 시퀀스 와 {2, 1, 1, 3, 4, 3, 5, 1} 최 장 비 엄격 한 증가 서브 시퀀스 의 결 과 는 다 릅 니 다. 따라서 코드 는:

function maxNum(arr){
    var max = 0;
    //      x  ，x     y     
    arr.sort(function(pre,after){
       return pre.x > after.x || (pre.x == after.x && pre.h > after.h);
    });
    //                
    var dp = [];
    for(var i=0;i

또한 최 장 증자 서열 의 길 이 를 어떻게 구 할 것 인가. 예 를 들 어 배열 A = [4, 1, 3, 7, 4, 2, 0, 9] 의 최 장 증자 서열 은 [1, 3, 4, 9] 또는 [1, 3, 7, 9] 이 고 최 장 증자 서열 의 길 이 는 4 가설 dp [i] 는 배열 A 의 아래 표 시 된 0 에서 i 라 는 서브 서열 에 나타 나 며 A [i] 를 끝 으로 하 는 최 장 증자 서열 의 길 이 를 나타 낸다. 예 를 들 어 dp [2] 는 [4, 1, 3] 을 나타 낸다.의 3 을 마지막 으로 하 는 증가 서브 시퀀스 의 길이 의 최대 치, [4, 1, 3] 의 3 을 마지막 으로 하 는 증가 서브 시퀀스 는 [1, 3] 이 므 로 dp [2] = = 2, 동 리 는 dp [0] = 1, dp [1] = 1, dp [3] = 3 이다. 그 다음 에 우 리 는 dp [4]: A [4] = 4 를 구하 고 [4, 1, 3, 7, 4] 에서 4 를 마지막 으로 하 는 증가 서브 시퀀스 의 길이 의 최대 치 를 요구한다. 우 리 는 A [4] 의 앞 에 A [4] 보다 작은 것 은 A [1] = 1 과 A [2] 가 있다.= = 3, 4 를 마지막 으로 하 는 증가 서브 시퀀스, 4 의 앞 에 있 는 것 은 3 일 수도 있 고 1 일 수도 있 기 때문에 dp [4] = Math. max (dp [1] + 1, dp [2] + 1, 1). dp [0 ~ A 의 길 이 를 구 한 후 dp 의 최대 치 는 배열 의 최 장 증가 서브 시퀀스 길이 이다.

var max = 0;
var dp = [];
for(var i=0;i