}
}
int s2 = 0;
int rights = 0;
for (int i = center + 1; i <= right; i++) {
rights += arr[i];
if (rights > s2) {
s2 = rights;
}
}
sum = s1 + s2;
if (sum < leftSum) {
sum = leftSum;
}
if (sum < rightSum) {
sum = rightSum;
}
}
return sum;
}
// 最大子段和动态规划法实现
public static void maxSumDp(int[] arr) {
int sum = 0, b = 0, n = arr.length, bestx = 0, besty = 0;
for (int i = 1; i <= n; i++) {
if (b > 0) {
b += arr[i - 1];
} else {
b = arr[i - 1];
bestx = i;
}
if (b > sum) {
sum = b;
besty = i;
}
}
System.out.println("动态规划算法最优值：" + sum);
System.out.println("最优解：" + bestx + "-->" + besty);
}
public static void main(String[] args) {
int[] arr = { 2,5,-3,4,-9,44,32,22,11,-30 };
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("最大子段和：");
System.out.println("分治算法最优值：" + maxSumDiv(arr, 0, arr.length - 1));
System.out.println("====================");
maxSumDp(arr);
System.out.println("====================");
maxSumSimp(arr, 0, 0);
}
}