The longest increasing subsequence and its optimal solution, total animal weight problem

subject

Find the length of the longest increasing subsequence in an array , Subsequences do not require continuity

• Through one dp Array to record the longest subsequence ending with this element in each array , Is the first i The longest subsequence at the end of an element =0～i-1 Within the scope of , Biti i Elements small ,dp The maximum length stored in +1
• First element dp[0]=1, The second element , If it's bigger than the first element , be dp[1]=2 Otherwise 1,…

The complexity is O(n*n) Solution ：

let arr = [2, 7, 5, 3, 6, 4, 5, 6, 1];

//O(n*n)
function maxSubLen(arr) {
    
  if (arr == null || arr.length == 0) {
    
    return 0;
  }
  let n = arr.length;
  //dp Array stores the longest subsequence value that ends with each element in the array 
  let dp = [];
  dp[0] = 1;
  let max = dp[0];
  for (let i = 1; i < n; i++) {
    
    let pre = 0;
    // Traverse the elements before each element , Find all smaller than this element , And dp The longest one 
    for (let j = 0; j < i; j++) {
    
      if (arr[j] < arr[i]) {
    
        pre = Math.max(pre, dp[j]);
      }
    }
    // Record the longest subsequence value that ends with this element 
    dp[i] = pre + 1;
    // The largest value in the duplicate check record 
    max = Math.max(max, dp[i]);
  }
  return max;
}
console.log(maxSubLen(arr));

The complexity is O(n*logn) Solution ：

• Add another array ends, Used to help dp Stores the length of the subsequence that ends with the current element ,ends The current element is stored in , The index is the length of the subsequence of the current element , Every time you traverse an element , I'll look for ends The first element larger than this element , Then put the element in that position , If not found , It means that the sequence length should be increased , Then the array length is increased by 1, Put it at the end

  • Let's say the array is [2, 7, 5, 3, 6, 4, 4, 6, 1];
  • ends[0]=2,dp[0]=2; The second element is 7,ends There is no better than 7 Big , Then the array is expanded , Sequence length plus 1,ends[1]=7,dp[1]=2;
  • The third element is 5,ends The first one in the competition 5 The big one is 7, Will 7 To cover with 5,ends[1]=5,d[2]=2
  • The fourth element is 3,ends The first one in the competition 3 The big one is 5, Will 5 To cover with 3,ends[1]=3,d[3]=2
  • The fifth element is 6,ends There is no better than 6 Large number , Then the array is expanded , Sequence length plus 1,ends[2]=6,dp[4]=3;
  • The sixth element is 4,ends The first one in the competition 4 The big one is 6, Will 6 To cover with 4,ends[2]=4,d[5]=3;
  • The seventh element is 4, Because the same is not an increasing sequence , So the same number directly covers ends The same element in ,ends[2]=4,d[6]=3;
  • The eighth number is 6,ends There is no better than 6 Large number , Then the array is expanded , Sequence length plus 1,ends[3]=6,dp[7]=4;
  • The ninth number is 1,ends The first one in the competition 1 The big one is 2, Will 2 To cover with 1,ends[0]=1,d[8]=1

• Because there is no larger element in the array than the current one, it will be expanded +1, Indicates the sequence length +1; The first element larger than the current element can be found in the array , Indexes +1 Is the sequence length at the end of the current element . therefore ends The elements in are incrementally ordered , You can find it by two points when investigating and dealing with it , So that the time complexity is O(logN);

• and ends Array storage logic , That is, it corresponds to the thinking of human search , such as [1,3,4,2];ends The first three numbers [1,3,4], The fourth number 2 The corresponding increment sequence should be 1,2, Put it on ends The position in is the first ratio 2 Big place [1,2,4], Indexes +1 Is the length

• In other words ： whenever ends An element larger than the current element was found in the array , Indicates that the sequence ending with the current element and the previous are broken （ Cannot form an increasing sequence ）, You have to recalculate , The new sequence is the previous one ends A sequence of elements smaller than the current element in plus the current element

let arr = [2, 7, 5, 3, 6, 4, 4, 6, 1];

function maxSubLen2(arr) {
    
  if (arr == null || arr.length == 0) {
    
    return 0;
  }
  let n = arr.length;
  let dp = [];
  let ends = [];
  dp[0] = 1;
  ends[0] = arr[0];
  //ends Array valid area 
  //0 To validSize-1 The range of two points 
  let max = dp[0];
  let validSize = 1;

  for (let i = 1; i < n; i++) {
    
    let cur = arr[i];
    
    // Bisect the position of the first element larger than the current element 
    let endsi = find(ends, validSize, cur);
    //-1 Indicates that no , explain ends The valid area of the array is less than num Of , It indicates that the valid area needs to be expanded 
    if (endsi == -1) {
    
      ends[validSize++] = cur;
      // The length after expansion is the sequence length of new elements 
      dp[i] = validSize;
    } else {
    
      ends[endsi] = cur;
      // The position of the first element larger than the current element +1, Is the length of the sequence ending with the current element 
      dp[i] = endsi + 1;
    }
    max = Math.max(max, dp[i]);
  }
  return max;
}

//ends Search in the valid area of the array >=num Leftmost position , No return -1, Two points search 
function find(ends, size, num) {
    
  let left = 0;
  let right = size - 1;

  let min = -1;
  let mid = 0;
  //left That is, the position of the first element larger than the current element 
  while (left <= right) {
    
    mid = left + parseInt((right - left) / 2);

    if (ends[mid] > num) {
    
      right = mid - 1;
    } else {
    
      // An element equal to the current element , Just replace the position directly 
      if (ends[mid] == num) {
    
        left = right = mid;
        break;
      }
      left = mid + 1;
    }
  }
  // console.log(left);
  // console.log(right);
  // Can't find , It indicates that the array elements are smaller than the current elements 
  if (left == size) {
    
    return -1;
  }
  return left;
}

subject

Yes n The weight of each animal is a1、a2、a3…an, This group of animals play the game of Luohan , It is required to select animals from left to right , The total weight of the animals on the left side of each animal does not exceed its own weight , Returns the maximum number of animals that can be selected , Find an efficient algorithm . Such as the 7 Animals , The weight from left to right is : 1, 3, 5, 7, 9, 11, 21 , At most 5 Animals :1, 3, 5, 9, 21, Note that the examples given in this topic are orderly , But the actual given array of animals , It could be disordered ,
It is required to select animals from left to right , And you can't disturb the original array

• The total weight of the animal on the left does not exceed its own weight , It must be an increasing sequence , The problem also becomes to find the longest increasing subsequence
• Similar to the above solution , Also through a dp The array records the longest length of each element that ends with this element , One ends Array , Used to record the index +1 The sum of the minimum weight corresponding to the length , At the same time index +1 The length of this is dp The length of the corresponding element
  • According to the content given by the topic , The first element is 1,dp[0]=1,ends[0]=1; The second element is 3,ends There is no bigger element in the , Then the array is expanded ,dp[1]=2,ends[1]=3+1=4, Said to 3 The total weight of the ending sequence
  • The third element is 5,ends There is no bigger element in the , Then the array is expanded ,dp[2]=3,ends[2]=3+1+5=9, Said to 5 The total weight of the ending sequence
  • The fourth element is 7, Find the ends There is a ratio in the array 7 Big , The query starts from the right side of the array, and the first ratio 7 The location of small elements , namely ends[1]=4, because 4+7>9, Explain with 7 The total weight of the sequence at the end is greater than 5 Total weight of the end , And because it is required to select the most quantity , So the smaller the total weight, the better , So the fourth element is not replaced , Only record the length , solid dp[3]=3（ends[1] The total length of 2+1）,ends[2]=9;
  • The fifth element is 9,ends There is no bigger element in the , Then the array is expanded ,dp[4]=4,ends[3]=3+1+5+9=18, Said to 9 The total weight of the ending sequence
  • The sixth element is 11, The query starts from the right side of the array, and the first ratio 11 The position of the small element is 9, namely ends[2]=9 because 9+11>18, Explain with 11 The total weight of the sequence at the end is greater than 9 Total weight of the end , Because it is required to select the maximum number , So the smaller the total weight, the better , So the sixth element is not replaced , Only record the length , solid dp[5]=4（ends[2] The length of +1）,ends[3]=18;
  • The seventh element is 21,ends There is no bigger element in the , Then the array is expanded ,dp[6]=5,ends[4]=18+21=39, Said to 21 The total weight of the ending sequence ; You can choose at most 5 individual
• because ends The content stored in represents , Every index +1 The minimum total weight of a sequence of lengths , So if you can't find anything larger than the current element , Explain that the array should be expanded , Sequence length +1, A fixed array must be incrementally ordered ; If an element is found to be larger than the current element , The current element cannot be linked , You need to create a new sequence , The new sequence is the first one smaller than the current element （ The total weight is smaller than the current element ） And the current element , At the same time, the total weight of the new sequence should be the smallest under the condition of the same length , To replace ends The total weight of the corresponding index in .

let arr3 = [1, 3, 5, 7, 9, 11, 21];

function maxSubLen3(arr) {
    
  if (arr == null || arr.length == 0) {
    
    return 0;
  }
  let n = arr.length;
  let dp = [];
  let ends = [];
  dp[0] = 1;
  ends[0] = arr[0];
  //ends Array valid area 
  //0 To validSize-1 The range of two points 
  let max = dp[0];
  let validSize = 1;

  for (let i = 1; i < n; i++) {
    
    let cur = arr[i];

    let endsi = find2(ends, validSize, cur);

    //ends The valid area of the array is less than num Of , It indicates that the valid area needs to be expanded 
    if (endsi == validSize - 1) {
    
      ends[validSize] = ends[validSize - 1] + cur;
      dp[i] = ++validSize;
    } else {
    
      // According to the first element smaller than this element and the sum of this element （ Cumulative weight ）, If it is smaller than the existing , Then replace 
      if (ends[endsi] + cur < ends[endsi + 1]) {
    
        ends[endsi + 1] = ends[endsi] + cur;
        // endsi + 1  Indicates the position of the element , Again +1 Length 
        dp[i] = endsi + 1 + 1;
      } else {
    
        dp[i] = endsi + 1 + 1;
      }
    }
    max = Math.max(max, dp[i]);
  }

  return max;
}

//ends The first ratio in the valid area of the array num Small position 
function find2(ends, size, num) {
    
  let left = 0;
  let right = size - 1;

  let mid = 0;
  let res = 0;
  while (left <= right) {
    
    mid = left + parseInt((right - left) / 2);

    if (ends[mid] <= num) {
    
      res = mid;
      left = mid + 1;
    } else {
    
      right = mid - 1;
    }
  }
  return res;
}
console.log(maxSubLen3(arr3));