hot100之动态规划下

最长递增子序列（300）

1. class Solution {
2.     public int lengthOfLIS(int[] nums) {
3.         int res = 1;
4.         for(int num : nums){
5.             int idx = findLarge(nums, res, num);
6.             nums[idx] = num;
7.             if (idx == res) res++;   
8.         }
9.         
10.         return res;
11.     }
13.     private int findLarge(int[] nums, int rig, int target){
14.         int lef = -1;
15.         while (lef+1 < rig){
16.             int mid = (lef + rig) / 2;
17.             if (nums[mid] < target){
18.                 lef = mid;
19.             }else rig = mid;
20.         }
22.         return rig;
23.     }
24. }

复制代码

• 分析
  

维护一个最小递增array（子序列）通过二分查找筛除坏值（比新插入值大）
利用二分查找优化查询
乘积的最大子数组（152）

1. class Solution {
2.     public int maxProduct(int[] nums) {
3.         int n = nums.length;
4.         int[] postive_dp = new int [n];
5.         int[] negative_dp = new int [n];
7.         postive_dp[0] = negative_dp[0] = nums[0];
8.         for(int i = 1; i < n; i++){
9.             postive_dp[i] =  max(postive_dp[i-1] * nums[i], negative_dp[i-1] * nums[i], nums[i]);
10.             negative_dp[i] = min(postive_dp[i-1] * nums[i], negative_dp[i-1] * nums[i], nums[i]);
11.         }
12.         
13.         int res = Integer.MIN_VALUE;
14.         for (int postive_num : postive_dp){
15.             res = Math.max(res, postive_num);
16.         }
17.         return res;
18.     }
20.     private int max(int val1, int val2, int val3){
21.         val2 = Math.max(val2, val3);
22.         return Math.max(val1, val2);
23.     }
25.     private int min(int val1, int val2, int val3){
26.         val2 = Math.min(val2, val3);
27.         return Math.min(val1, val2);
28.     }
29. }

复制代码

• 分析
  

因为num有两种状态，即使前值算出来很小 但通过乘负数可以将大局逆转吧
所以维护最大正数和最小负数两个dp，都是潜力
同样也可以优化内存， 因为只依赖前一个状态
分割等和子集（416）

1. class Solution {
2.     public boolean canPartition(int[] nums) {
3.         int sum = 0;
4.         for (int num: nums){
5.             sum += num;
6.         }
7.         if (sum % 2 != 0) return false;
9.         int target = sum / 2;
10.         boolean[] dp = new boolean[target+1];
11.         dp[0] = true;
12.         for (int num : nums){
13.             for (int subSum = target; subSum >= num; subSum--){
14.                 dp[subSum] |= dp[subSum - num];
15.                 if (dp[target]) return true;
16.             }
17.         }
18.         return false;
19.     }
20. }

复制代码

• 分析
  

背包问题
最长有效括号(32)

1. class Solution {
2.     public int longestValidParentheses(String s) {
3.         int n = s.length();
4.         Deque<Integer> stack = new ArrayDeque<>();
5.         stack.push(-1); // 避免第一个数值是左括号， 无值弹出
6.         int res = 0;
8.         for (int i = 0; i < n; i++){
9.             if (s.charAt(i) == '('){
10.                 stack.push(i);
11.             }else{
12.                 stack.pop();
13.                 if (stack.isEmpty()){
14.                     stack.push(i);
15.                 }else{
16.                     res = Math.max(res, i - stack.peek());
17.                 }
18.             }
19.         }
21.         return res;
22.     }
23. }

复制代码

• 分析
  

没什么好想法，就用栈了
java 里栈的优化似乎不好，不如双端队列

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除