首页 > 代码库 > DP之子序列问题
DP之子序列问题
最近算法课又学习了一遍动态规划，看了一些求子序列的问题，特意集中mark一下以作备忘.。
最长上升子序列
- 问题描述
对于给定的整数数组序列，若它的一个子序列的元素是升序排列的，则称这个子序列是一个上升子序列。问题要求对于一给定整数数组，要求找到一个它的最长上升子序列。
- 算法实现
设A为给定的数组，A[i] 表示数组A的第i个元素，DP[i]表示表示以A[i]为结尾的最长上升子序列的长度，初始化DP[i]=0(i=1,2.....len(A)),则有状态转移方程：DP[i]=max{1,DP[j]+1}(j=1,2,3...i-1 ,且A[j] < A[i])。
最大和连续子序列
- 问题描述
寻找数组的一个连续子序列，使得这个子序列的和是所有连续子序列中的和最大的。
- 算法实现
public int maxSubArray(int[] A) { int sum = 0; int max = MIN; for (int i = 0; i < A.length; i++) { sum += A[i]; if (sum > max) max = sum; if (sum < 0) sum = 0; } return max;}最大积连续子序列
- 问题描述
寻找数组的一个连续子序列，使得这个子序列的积是所有连续子序列中的积最大的。
- 算法实现
最大积问题需不断的记录两个值，max以及min。max记录当前最大的正积，min记录当前最小负积，或者是1.
int maxProduct(int[] A) { int x = 1; int max = 1; int min = 1; for (int i = 0; i < A.length; i++) { if (A[i] == 0) { max = 1; min = 1; } else if (A[i] > 0) { max = max * A[i]; min = Math.min(min * A[i], 1); } else { int temp = max; max = Math.max(min * A[i], 1); min = temp * A[i]; } if (max > x) x = max; } return x;}
DP之子序列问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。