Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function maxIncreasingSeq() {
- var sequence = [2, 4, 3, 5, 1, 7, 6, 9, 8, 102, 11, 12, 13, 15 ,17, 18];
- var length = [1];
- var predecessor = [-1];
- var maxLength = 1;
- for (var i = 1; i < sequence.length; i++) {
- var currElement = sequence[i];
- length[i] = 1;
- var onlyFirstTime = true;
- predecessor[i] = -1;
- for (var j = i-1; j >= 0; j--) {
- if(sequence[j] < currElement) {
- if(maxLength <= length[j] + 1) {
- maxLength = length[j] + 1;
- if(onlyFirstTime) {
- predecessor[i] = j;
- onlyFirstTime = false;
- }
- }
- length[i] = maxLength;
- }
- }
- }
- console.log(length);
- console.log(predecessor);
- console.log("Max Length is: %d", length[length.length-1]);
- console.log("The array is: ");
- var maxSequence = [];
- Array.prototype.max = function () {
- return Math.max.apply(null, this);
- }
- var initialIndex = length.indexOf(length.max());
- maxSequence.push(sequence[initialIndex]);
- var initialPredecessor = predecessor[initialIndex];
- while(maxSequence.length != length[length.length-1]) {
- maxSequence.push(sequence[initialPredecessor]);
- initialPredecessor = predecessor[initialPredecessor];
- }
- console.log(maxSequence);
- }
- maxIncreasingSeq();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement