1.LeetCode HOT 87，88，89，90
300.最长递增子序列
给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1// 动态规划// dp[i]表示前i个元素的最长递增子序列长度publicintlengthOfLIS(int[]nums){intres=-1;int[]dp=newint[nums.length];Arrays.fill(dp,1);for(inti=0;i<nums.length;i++){for(intj=0;j<i;j++){if(nums[j]<nums[i])dp[i]=Math.max(dp[j]+1,dp[i]);}res=Math.max(res,dp[i]);}returnres;}// 二分加贪心 // d[i]表示长度为i的最长递增子序列末尾元素最小值 public int lengthOfLIS(int[] nums) { int[] d = new int[nums.length + 1]; int len = 1; d[len] = nums[0]; for(int i = 1; i < nums.length; i++){ if(d[len] < nums[i]){ // 表明递增子序列可以扩张 d[++len] = nums[i]; }else { // 表明长度1-len之间可替换掉最小值,d数组有序可用二分 int l = 1, r = len; while (l < r){ int mid = (l + r) >> 1; if(d[mid] >= nums[i])r = mid; else l = mid + 1; } d[l] = nums[i]; } } return len; }152.乘积最大子数组
给你一个整数数组nums，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个32-位整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。publicintmaxProduct(int[]nums){// 维护两个最大值最小值数组int[]dMin=newint[nums.length],dMax=newint[nums.length];dMax[0]=nums[0];dMin[0]=nums[0];intres=dMax[0];for(inti=1;i<nums.length;i++){intt1=dMax[i-1]*nums[i],t2=dMin[i-1]*nums[i];dMax[i]=Math.max(Math.max(t1,t2),nums[i]);dMin[i]=Math.min(Math.min(t1,t2),nums[i]);res=Math.max(res,dMax[i]);}returnres;}416.分割等和子串
给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。publicbooleancanPartition(int[]nums){intsum=Arrays.stream(nums).sum();if(sum%2==1)returnfalse;intx=sum/2;int[][]history=newint[nums.length][x+1];for(int[]ints:history){Arrays.fill(ints,-1);}returndfs(nums,0,x,history);}// 记忆化搜索booleandfs(int[]nums,inti,inttargrt,int[][]history){if(i==nums.length)returntargrt==0;if(targrt==0){returntrue;}if(history[i][targrt]!=-1)returnhistory[i][targrt]==1;booleantmp;if(targrt-nums[i]>=0){tmp=dfs(nums,i+1,targrt-nums[i],history)||dfs(nums,i+1,targrt,history);;}else{tmp=dfs(nums,i+1,targrt,history);}history[i][targrt]=tmp?1:0;returntmp;}// dp(i,j)表示前i个的值能否等于j// dp(i - 1, j - num[i])// dp(i - 1, j)// 边界dp(i,0) = true// 第一个dp(0, nums[0]) = truepublicbooleancanPartition(int[]nums){intsum=Arrays.stream(nums).sum();if(sum%2==1)returnfalse;intx=sum/2;if(Arrays.stream(nums).max().getAsInt()>x)returnfalse;// 转换成数组中是否正好有和为x的0 1背包问题boolean[][]dp=newboolean[nums.length][x+1];dp[0][nums[0]]=true;for(boolean[]booleans:dp){booleans[0]=true;}for(inti=1;i<nums.length;i++){for(intj=0;j<=x;j++){if(j>=nums[i]){dp[i][j]=dp[i-1][j-nums[i]]||dp[i-1][j];}elsedp[i][j]=dp[i-1][j];}}returndp[nums.length-1][x];}publicbooleancanPartition(int[]nums){intsum=Arrays.stream(nums).sum();if(sum%2==1)returnfalse;intx=sum/2;if(Arrays.stream(nums).max().getAsInt()>x)returnfalse;// 转换成数组中是否正好有和为x的0 1背包问题boolean[]dp=newboolean[x+1];dp[0]=true;for(inti=1;i<nums.length;i++){for(intj=x;j>=nums[i];j--){// dp状态更新只和上一层状态有关，因此可以优化为一维数组，同时状态的更新取决于取不取当前数字，如果取那么dp[j-nums[i]]，不取那么就是dp[j]，// 因为数组保存的是上一层数据，从高向低更新则不会被覆盖// 同时j < nums[i]时状态就和上一层一样，因此不用更新dp[j]=dp[j]||dp[j-nums[i]];}}returndp[x];}2.微服务学习
1）Dubbo和Feign对比
思考：使用Dubbo时就像在使用Spring一样，可以像注入本地Bean一样直接注解注入Service，调用Service的接口编写Controller,而Feign更像是一种代理，一个配置化的HTTP客户端，通过拼接HTTP请求获取结果后封装。
这是因为RPC（如Dubbo）和 HTTP REST（如Spring Cloud Feign）两种微服务通信模式在设计和体验上的核心差异。
如图所示，Feign实际生成“HTTP调用”代理对象，通过代理对象将方法调用转换成HTTP请求，而后到服务注册中心通过负载均衡器选择实例发送HTTP请求后将结果封装。开发者需要关注接口定义；Dubbo是生成代理对象，而后将代理对象内部直接序列化，通过服务注册中心反序列化到调用者，因此可以实现类似bean注入的效果，但是服务提供方和消费方需定义统一接口。
下面我们展开讲讲图中的关键点：
1. 协议与透明性
- Dubbo：是高性能的二进制RPC框架。它在TCP层之上自定义了协议，将方法名、参数类型、参数值等精确序列化成二进制流进行传输。其核心设计目标就是“让远程调用像本地调用一样”，因此它极力在框架层面隐藏所有网络细节。
- Spring Cloud OpenFeign：本质上是一个声明式的HTTP客户端。它基于通用的HTTP/HTTPS协议，将方法调用转化为标准的HTTP请求（GET/POST等）。HTTP协议是文本化的、无状态的，因此Feign的设计更偏向轻量、灵活和契约化，开发者需要对“这是一次HTTP调用”有基本认知。
2.代理与注入
Dubbo的@Reference：
深度集成：Dubbo与Spring的集成（
dubbo-spring-boot-starter）非常深入。它创建的代理对象不仅负责网络通信，还完全模拟了本地接口的行为。全能代理：这个代理背后替你完成了：查找注册中心、负载均衡、序列化、网络传输、反序列化、异常处理等所有步骤。你拿到的是一个“看起来就是本地实现”的对象。
// 服务接口（共享API包）publicinterfaceOrderService{OrderDTOcreateOrder(OrderRequestrequest);}// 服务提供者@DubboService(version="1.0.0")publicclassOrderServiceImplimplementsOrderService{@OverridepublicOrderDTOcreateOrder(OrderRequestrequest){// 业务逻辑}}// 服务消费者@ServicepublicclassPaymentService{@DubboReference(version="1.0.0")privateOrderServiceorderService;publicvoidpay(LongorderId){OrderDTOorder=orderService.createOrder(newOrderRequest(orderId));}}
Spring Cloud的@FeignClient：
- 专注HTTP：它创建的代理对象，核心功能是将你的Java方法调用，翻译成一个HTTP请求模板。
- 分工明确：负载均衡（LoadBalancer）、服务发现（Nacos）是其他组件负责的。Feign代理需要和这些组件协作。你注入的更像一个“聪明的HTTP客户端模板”。
// 服务提供者（Spring MVC）@RestController@RequestMapping("/products")publicclassProductController{@GetMapping("/{id}")publicResponseEntity<ProductDTO>getProduct(@PathVariableLongid){ProductDTOproduct=productService.findById(id);returnResponseEntity.ok(product);}}// 服务消费者（OpenFeign）@FeignClient(name="product-service")publicinterfaceProductClient{@GetMapping("/products/{id}")ProductDTOgetProduct(@PathVariable("id")Longid);}DTO product = productService.findById(id);
return ResponseEntity.ok(product);
}
}
// 服务消费者（OpenFeign）
@FeignClient(name = “product-service”)
public interface ProductClient {
@GetMapping(“/products/{id}”)
ProductDTO getProduct(@PathVariable(“id”) Long id);
}
