通过网站赚钱,杭州网站设计手机,产品推广文案怎么写,想学网站建设开发目录 基本概念
最长递增子序列#xff08;中等#xff09;
最大子数组和#xff08;中等#xff09; 基本概念
重叠子问题
一个问题可以被分解为多个子问题#xff0c;并且这些子问题在求解过程中会被多次重复计算。例如#xff0c;在计算斐波那契数列时#xff0c;…目录 基本概念
最长递增子序列中等
最大子数组和中等 基本概念
重叠子问题
一个问题可以被分解为多个子问题并且这些子问题在求解过程中会被多次重复计算。例如在计算斐波那契数列时斐波那契数 F(n) 的计算需要先计算 F(n - 1) 和 F(n - 2)而计算 F(n - 1) 又需要计算 F(n - 2) 和 F(n - 3)这里 F(n - 2) 就是重叠子问题。
最优子结构
问题的最优解可以由子问题的最优解组合而成。也就是说如果一个问题的最优解包含了子问题的解那么这些子问题的解本身对于它们各自的子问题来说也必须是最优的。以背包问题为例要得到能装入背包的最大价值物品组合的最优解这个最优解取决于装入背包部分容量时选择不同物品所得到的子问题的最优解。
解题步骤
确定状态定义问题的状态状态通常是问题求解过程中的某个中间结果或者某个阶段的情况描述。比如在爬楼梯问题中状态可以定义为爬到第 n 级楼梯时的不同方法数这里的 n 就是状态变量。建立状态转移方程根据问题的最优子结构性质找出状态之间的递推关系即从一个或多个已知状态推导出另一个状态的方程。在斐波那契数列问题中状态转移方程就是 F(n) F(n - 1) F(n - 2)。确定边界条件明确问题的初始状态或最小子问题的解这些边界条件是递归求解的基础。对于斐波那契数列边界条件是 F(0) 0F(1) 1。 最长递增子序列中等
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 。
一维动态规划
int[] nums {10,9,2,5,3,7,101,18};
dp默认都是1
dp[2] 1
dp[3] max(dp[3], dp[2]1) 2
dp[4] max(dp[4], dp[2] 1) 2
dp[5] max(dp[5], dp[2] 1) 2 max(dp[5], dp[3] 1) 3 max(dp[5], dp[4] 1) 3
dp[6] max(dp[6], dp[2] 1) 2 max(dp[6], dp[3] 1) 3 max(dp[6], dp[4] 1) 3 max(dp[6], dp[5] 1) 4 public int lengthOfLIS(int[] nums) {if(nums.length 1){return 1;}int max 0;int[] dp new int[nums.length];Arrays.fill(dp, 1);for (int i 1; i nums.length; i) {for (int j 0; j i; j) {if(nums[i] nums[j]){dp[i] Integer.max(dp[i], dp[j]1);}}max Integer.max(max, dp[i]);}return max;} 最大子数组和中等 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组是数组中的一个连续部分。 示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组 [4,-1,2,1] 的和最大为 6 。
示例 2
输入nums [1]输出1
示例 3
输入nums [5,4,-1,7,8]输出23
class Solution {public int maxSubArray(int[] nums) {int pre 0, maxAns nums[0];for (int x : nums) {pre Math.max(pre x, x);maxAns Math.max(maxAns, pre);}return maxAns;}
}
