动态规划求最大字段java -2,11,-4,13,-5,-2 求出最大字段和。 当字段和小于0时直接对于下一值
时间: 2024-12-17 10:18:33 浏览: 9
动态规划求解这种问题时,我们需要对数组进行分段处理,每一段都是一个非负的连续子序列。针对您的输入 `[-2, 11, -4, 13, -5, -2]` 和规则“当字段和小于0时直接对于下一值”,我们可以采用类似Kadane's Algorithm的思想,不过稍微修改一下策略,在遇到负数导致和变小的时候,立即切换到下一个元素,而不是继续累积。
下面是相应的Java代码实现:
```java
public class MaxSubArrayNoNegative {
public static int maxNonNegativeSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int currentSum = 0; // 当前非负子数组和
int maxSum = nums[0]; // 最大非负子数组和
for (int num : nums) {
if (currentSum <= 0) { // 当和为负时,清零并从下个元素开始
currentSum = num;
} else {
currentSum += num; // 否则累加当前元素
}
maxSum = Math.max(maxSum, currentSum); // 更新最大非负子数组和
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {-2, 11, -4, 13, -5, -2};
System.out.println("Max non-negative subarray sum is: " + maxNonNegativeSubArray(nums));
}
}
```
运行此代码会得到结果 `13`,这是在数组中所有非负子数组和中最大的那个。
阅读全文