Number conclusion LC skimming review - 1

217. There are duplicate elements

• There are duplicate elements
• Use Set Of size and Array Of length Just judge .
• At first, we tried to divide and conquer , But the problem cannot be decomposed into the smallest problem , Because there are no duplicate elements in the left array , There are no duplicate elements on the right , It does not mean that there are no duplicate elements in the original array （ That is, when the left and right arrays contain the same elements , Such as [1,2,3,1]
• Traversable arrays , Use hashMap Mark values , If duplicate marks are found, exit the traversal .
• You can sort against arrays , Scan whether adjacent elements have the same value , Time for space .

53. Maximum subarray and

• Maximum subarray and

• Dynamic gauge ,dp[i] The subscript in the input array is i The largest subarray and .

• Divide and conquer , Bisection decomposition array , And derive the parent optimal solution from the child optimal solution

  const mid = Math.floor((l + r) / 2);
     let L_res = R_res= {
        
         iSum: 0,
         lSum: 0,
         rSum: 0,
         aSum: 0
     };
     if(mid - 1 >= l) {
        
         L_res = getlmr(arr, l, mid - 1);
     }
     if(mid <= r) {
        
         R_res = getlmr(arr, mid, r)
     }
     const {
         iSum: L_iSum, lSum: L_lSum, rSum: L_rSum, aSum: L_aSum} = L_res
     const {
         iSum: R_iSum, lSum: R_lSum, rSum: R_rSum, aSum: R_aSum} = R_res;
     return {
        
         iSum: Math.max(L_iSum, R_iSum, L_rSum + R_lSum),
         lSum: Math.max(L_lSum, L_aSum + R_lSum),
         rSum: Math.max(R_rSum, R_aSum + L_rSum),
         aSum: L_aSum + R_aSum,
     }