Scala implementation


  • 0
    Q
    // DP
    def maxEnvelopes3(envelopes: Array[Array[Int]]): Int = {
    	val sortedEnvelopes = envelopes.sortBy(x => x(0))
    
    	val length = envelopes.length
    	if(length < 2)
    		length
    	else{	
    		val res = (length - 2 to 0 by -1).foldLeft(Map(length - 1 -> 1)){
    			(acc, i) =>
    				val e = sortedEnvelopes(i)
    				val maxForCur = acc.foldLeft(1){
    					(ac, ee) =>
    						val w = sortedEnvelopes(ee._1)(0)
    						val h = sortedEnvelopes(ee._1)(1)
    						if(w> e(0) && h > e(1))
    							Math.max(ee._2+1, ac)
    						else
    							ac
    				}
    				acc + (i -> maxForCur)
    		}
    
    		res.map(_._2).max
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.