用分治法求数组的最大子序列和,用Java实现
时间: 2024-05-14 16:12:42 浏览: 13
以下是Java实现代码:
```
public class MaxSubArray {
public int maxSubArray(int[] nums) {
return divide(nums, 0, nums.length - 1);
}
private int divide(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) / 2;
int leftSum = divide(nums, left, mid);
int rightSum = divide(nums, mid + 1, right);
int crossSum = cross(nums, left, right, mid);
return Math.max(Math.max(leftSum, rightSum), crossSum);
}
private int cross(int[] nums, int left, int right, int mid) {
int leftSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
int rightSum = Integer.MIN_VALUE;
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
return leftSum + rightSum;
}
}
```
使用分治法,将数组分为两部分,分别求出左半部分的最大子序列和、右半部分的最大子序列和和跨越中心点的最大子序列和,最后取三者的最大值即可。跨越中心点的最大子序列和可以通过从中心点向左、向右扩展求出。时间复杂度为O(nlogn)。