Tree heights

Min # to remove to keep sorted

by Aaron Li

HTML

<link rel="stylesheet" href="https://s3.amazonaws.com/kiddsoftware-jsfiddle/mocha-1.9.0.css">
<script src="https://s3.amazonaws.com/kiddsoftware-jsfiddle/mocha-1.9.0.js"></script>
<script src="	 https://s3.amazonaws.com/kiddsoftware-jsfiddle/chai-1.5.0.js"></script>
<script src="https://s3.amazonaws.com/kiddsoftware-jsfiddle/chai-jquery.js"></script>

<div id="mocha"></div>

CSS

p {
    padding: 0;
    margin: 0;
}

div:nth-child(1) > p { 
    color: green;
}

div::nth-child(2) > p { 
    color: blue;
}

JavaScript

// Configure Mocha, telling both it and chai to use BDD-style tests. 
mocha.setup("bdd");
chai.should();

//Testable function
//A solution to compute minimum number of removal to make tree height sorted
function solution(A)  {
    var result = 0;
    var lis = [];
    for (var i=0; i<A.length; i++) {
        lis[i] = 1;
    }
    for (var i=1; i<A.length; i++) {
        for (var j=0; j<i;j++) {
            if　(A[i]>A[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
    for (var i=0; i<A.length; i++) {
        if (result < lis[i]) {
            result = lis[i];
        }
    }
    return A.length - result;
};

describe('Unit Tests of min # to remove to have tree height sorted ', function(){
    it('min # is 2 when input as [5,6,1,7,4]', function(){
        var i = [5, 6, 1, 7, 4];
        var e = 2;
        e.should.equal(solution(i));
    });
    it('min # is 2 when input as [3,9,4,8,5,6]', function(){
        var i = [3,9,4,8,5,6];
        var e = 2;
        e.should.equal(solution(i));
    });
});

// Run all our test suites.  Only necessary in the browser.
mocha.run();