剑指offer-73、连续⼦数组的最⼤和(⼆)
输⼊⼀个⻓度为n 的整型数组array ，数组中的⼀个或连续多个整数组成⼀个⼦数组，找到⼀个具有 示例 1 示例 2 通过三重循环枚举所有可能的子数组，使用三重循环枚举所有可能的子数组起始和结束位置，计算每个子数组的和 在暴力法基础上优化，利用前缀和在计算子数组和时复用之前的结果，减少一层循环 采用分治思想，将问题分解为更小的子问题 将问题分解为左半部分、右半部分和跨越中间的三部分 即递归求解左右子数组，合并时处理跨越中间的情况 遍历数组，维护当前子数组和，根据规则重置或扩展当前子数组 假设现在有 n 个元素，突然加上⼀个元素，变成 n+1 个元素，对连续⼦数组的最⼤和有什么影响呢？ 我们只需要知道以每⼀个元素结尾的最⼤连续⼦数组，再维护⼀个最⼤的值即可。 假设数组为num[] ，⽤ dp[i] 表示以下标 i 为终点的最⼤连续⼦数组和，遍历每⼀个新的元素nums[i+1] ，以 num[i+1] 为连续⼦数组的情况只有两种： 所以以nums[n] 结尾的最⼤连续⼦数组和为： dp[i] = max( dp[i-1] + num[i], num[i]) 在计算的过程中，需要维护⼀个最⼤的值，并且把该连续⼦数组的左边界以及右边界维护好，最后根据维护的区间返回。题⽬描述
最⼤和的连续⼦数组。
输⼊：[1,-2,3,10,-4,7,2,-5]
返回值：[3,10,-4,7,2]
说明：经分析可知，输⼊数组的⼦数组[3,10,-4,7,2]可以求得最⼤和为18，故返回[3,10,-4,7,2]
输⼊：[1]
返回值：[1]思路及解答
暴力枚举
public class Solution {
public int[] findMaxSubarray(int[] array) {
if (array == null || array.length == 0) {
return new int[0];
}
int n = array.length;
int maxSum = Integer.MIN_VALUE;
int start = 0, end = 0;
// 第一重循环：子数组起始位置
for (int i = 0; i < n; i++) {
// 第二重循环：子数组结束位置
for (int j = i; j < n; j++) {
int currentSum = 0;
// 第三重循环：计算子数组和
for (int k = i; k <= j; k++) {
currentSum += array[k];
}
// 更新最大和及位置（优先选择长度更长的）
if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {
maxSum = currentSum;
start = i;
end = j;
}
}
}
// 构建结果数组
int[] result = new int[end - start + 1];
System.arraycopy(array, start, result, 0, result.length);
return result;
}
}优化枚举法（前缀和思想）
public class Solution {
public int[] findMaxSubarray(int[] array) {
if (array == null || array.length == 0) {
return new int[0];
}
int n = array.length;
int maxSum = Integer.MIN_VALUE;
int start = 0, end = 0;
// 外层循环：子数组起始位置
for (int i = 0; i < n; i++) {
int currentSum = 0;
// 内层循环：从起始位置向后累加
for (int j = i; j < n; j++) {
currentSum += array[j]; // 复用之前计算的结果
// 更新最大和（优先选择长度更长的）
if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {
maxSum = currentSum;
start = i;
end = j;
}
}
}
return buildResult(array, start, end);
}
private int[] buildResult(int[] array, int start, int end) {
int[] result = new int[end - start + 1];
System.arraycopy(array, start, result, 0, result.length);
return result;
}
}分治法（递归思维）
public class Solution {
public int[] findMaxSubarray(int[] array) {
if (array == null || array.length == 0) {
return new int[0];
}
Result result = findMaxSubarrayHelper(array, 0, array.length - 1);
return buildResult(array, result.start, result.end);
}
private Result findMaxSubarrayHelper(int[] array, int left, int right) {
// 基准情况：单个元素
if (left == right) {
return new Result(left, right, array[left]);
}
int mid = left + (right - left) / 2;
// 递归求解左右两部分
Result leftResult = findMaxSubarrayHelper(array, left, mid);
Result rightResult = findMaxSubarrayHelper(array, mid + 1, right);
Result crossResult = findMaxCrossingSubarray(array, left, mid, right);
// 返回三者中的最大值（长度优先）
return getMaxResult(leftResult, rightResult, crossResult);
}
private Result findMaxCrossingSubarray(int[] array, int left, int mid, int right) {
// 向左扩展找最大和
int leftSum = Integer.MIN_VALUE;
int sum = 0;
int maxLeft = mid;
for (int i = mid; i >= left; i--) {
sum += array[i];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
// 向右扩展找最大和
int rightSum = Integer.MIN_VALUE;
sum = 0;
int maxRight = mid + 1;
for (int i = mid + 1; i <= right; i++) {
sum += array[i];
if (sum > rightSum) {
rightSum = sum;
maxRight = i;
}
}
return new Result(maxLeft, maxRight, leftSum + rightSum);
}
private Result getMaxResult(Result r1, Result r2, Result r3) {
Result maxResult = r1;
if (r2.sum > maxResult.sum || (r2.sum == maxResult.sum && (r2.end - r2.start) > (maxResult.end - maxResult.start))) {
maxResult = r2;
}
if (r3.sum > maxResult.sum || (r3.sum == maxResult.sum && (r3.end - r3.start) > (maxResult.end - maxResult.start))) {
maxResult = r3;
}
return maxResult;
}
private int[] buildResult(int[] array, int start, int end) {
int[] result = new int[end - start + 1];
System.arraycopy(array, start, result, 0, result.length);
return result;
}
// 辅助类存储子数组结果
class Result {
int start, end, sum;
Result(int s, int e, int sum) {
this.start = s;
this.end = e;
this.sum = sum;
}
}
}动态规划-Kadane算法（最优解）
public class Solution85 {
public int[] FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int[array.length];
dp[0] = array[0];
int maxsum = dp[0];
int left = 0, right = 0;
int maxLeft = 0, maxRight = 0;
for (int i = 1; i < array.length; i++) {
right++;
dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
if (dp[i - 1] + array[i] < array[i]) {
left = right;
}
// 更新最⼤值以及更新最⼤和的⼦数组的边界
if (dp[i] > maxsum || dp[i] == maxsum && (right - left + 1) > (maxRight - maxLeft + 1)) {
maxsum = dp[i];
maxLeft = left;
maxRight = right;
}
}
// 保存结果
int[] res = new int[maxRight - maxLeft + 1];
for (int i = maxLeft, j = 0; i <= maxRight; i++, j++) {
res[j] = array[i];
}
return res;
}
}
