题解 | #最长上升子序列(一)# [S-P0]

最长上升子序列(一)

http://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f

import java.util.*;

// time O(n^2) solution.
public class Solution {
    public int LIS (int[] arr) {
      if (arr.length <= 1) return arr.length;
      
      // F(i): length of LCI ending with arr[i].
      int[] mem = new int[arr.length];
      Arrays.fill(mem, 1);
      
      // F(i) = MAX(F(j)) + 1, where j < i and arr[j] < arr[i]
      int max = 0;
      for (int i = 1; i < mem.length; i++) {
        for (int j = 0; j < i; j++) {
          if (arr[j] < arr[i]) {
            mem[i] = Math.max(mem[i], mem[j] + 1);
            // 记录global max
            max = Math.max(max, mem[i]);
          }
        }
      }
      
      return max;
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务