Java用动态规划最大子序列和的问题,并输出最大子序列
时间: 2024-05-19 07:12:38 浏览: 10
解法如下:
1. 定义状态:我们定义 dp[i] 表示以第 i 个数结尾的最大子序列和。
2. 状态转移方程:对于第 i 个数,它有两种选择,要么加入前面的子序列中,要么不加入。如果加入,那么 dp[i] = dp[i-1] + nums[i],如果不加入,那么 dp[i] = nums[i]。因此,我们可以写出状态转移方程:
dp[i] = max(dp[i-1] + nums[i], nums[i])
3. 初始状态:dp[0] = nums[0]
4. 最终结果:我们需要遍历 dp 数组,找到最大的 dp[i] 值,并记录对应的下标 i。
5. 最大子序列的输出:从 i 开始,沿着 dp 数组往前遍历,将所有加入子序列的数添加到一个数组中即可。
Java 代码如下:
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int maxSum = dp[0], end = 0;
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
if (dp[i] > maxSum) {
maxSum = dp[i];
end = i;
}
}
List<Integer> list = new ArrayList<>();
int sum = 0;
for (int i = end; i >= 0; i--) {
sum += nums[i];
if (sum == maxSum) {
list.add(nums[i]);
break;
}
list.add(nums[i]);
}
Collections.reverse(list);
System.out.println("最大子序列为:" + list);
return maxSum;
}