java用动态规划写数组最大连续子序列和
时间: 2023-07-08 11:11:22 浏览: 63
下面是使用动态规划来解决Java中最大连续子序列和问题的代码:
```java
public static int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
```
其中,`dp[i]` 表示以 `nums[i]` 结尾的最大子序列和,初始化为 `nums[0]`,然后从 `i=1` 开始遍历数组,根据状态转移方程 `dp[i] = max(nums[i], dp[i-1] + nums[i])` 计算 `dp[i]` 的值,同时更新最大子序列和 `maxSum`。
最后,返回 `maxSum` 即可。
相关问题
最大子列和问题java动态规划
最大子列和问题是一个经典的算法问题,它的目标是在一个给定的整数序列中找到一个连续子序列,使得该子序列的和最大。下面是使用动态规划解决最大子列和问题的Java代码示例:
```java
public class MaxSubarraySum {
public static int maxSubarraySum(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSum = maxSubarraySum(nums);
System.out.println("Max subarray sum: " + maxSum); // 输出:6
}
}
```
上述代码中,我们使用两个变量`maxSum`和`currentSum`来记录当前的最大子列和和当前的子列和。我们遍历整个数组,对于每个元素,我们比较将其与当前子列和相加后的结果,以及当前元素本身,取较大值作为新的当前子列和。同时,我们也更新最大子列和。最后,返回最大子列和即可。
用java二叉树的最长连续子序列问题
对于一棵二叉树,我们可以定义其最长连续子序列(LCS)为从根节点开始,沿着任意路径向下遍历,使得经过的结点值连续递增或递减的最长路径长度。
为了求解二叉树的 LCS,我们可以使用递归的思想。具体来说,我们可以定义一个递归函数 dfs,其参数为当前结点和上一个结点的值 pre,并返回以当前结点为结尾的 LIS 长度和 LDS 长度。对于一个结点 node,如果 node.val = pre + 1,则可以将当前结点加入到 LIS 中;如果 node.val = pre - 1,则可以将当前结点加入到 LDS 中。如果 node.val 既不是 pre + 1 也不是 pre - 1,则需要重新开始计算 LCS 长度。最终的 LCS 长度即为所有以各个结点为结尾的 LIS 和 LDS 长度的最大值。
下面是一个 Java 代码实现:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int longestConsecutive(TreeNode root) {
if (root == null) {
return 0;
}
int[] res = dfs(root, root.val - 1);
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node, int pre) {
if (node == null) {
return new int[]{0, 0};
}
int[] left = dfs(node.left, node.val);
int[] right = dfs(node.right, node.val);
int[] cur = new int[]{1, 1};
if (node.val == pre + 1) {
cur[0] = Math.max(cur[0], left[0] + 1);
cur[1] = Math.max(cur[1], right[1] + 1);
} else if (node.val == pre - 1) {
cur[0] = Math.max(cur[0], right[0] + 1);
cur[1] = Math.max(cur[1], left[1] + 1);
}
return cur;
}
}
```
其中 dfs 函数返回一个长度为 2 的数组,第一个元素表示以当前结点为结尾的 LIS 长度,第二个元素表示以当前结点为结尾的 LDS 长度。对于每个结点,我们分别计算其向左子树和右子树的 LIS 和 LDS 长度,并根据当前结点与上一个结点的大小关系来更新当前结点的 LIS 和 LDS 长度。最终返回根节点的 LIS 和 LDS 长度的最大值即可。