剑指offer-73、连续⼦数组的最⼤和(⼆)
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个⻓度为n 的整型数组array ，数组中的⼀个或连续多个整数组成⼀个⼦数组，找到⼀个具有<br>
最⼤和的连续⼦数组。</p>
<ol>
<li>⼦数组是连续的，⽐如 的⼦数组有 ， 等等，但是 不是⼦数组</li>
<li>如果存在多个最⼤和的连续⼦数组，那么返回其中⻓度最⻓的，该题数据保证这个最⻓的只存在⼀个</li>
<li>该题定义的⼦数组的最⼩⻓度为1 ，不存在为空的⼦数组，即不存在[]是某个数组的⼦数组</li>
<li>返回的数组不计⼊空间复杂度计算</li>
</ol>
<p>示例 1<br>
输⼊：<br>
返回值：<br>
说明：经分析可知，输⼊数组的⼦数组可以求得最⼤和为18，故返回</p>
<p>示例 2<br>
输⼊：<br>
返回值：</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力枚举">暴力枚举</h3>
<p>通过三重循环枚举所有可能的子数组，使用三重循环枚举所有可能的子数组起始和结束位置，计算每个子数组的和</p>
<pre><code class="language-java">public class Solution {
public int[] findMaxSubarray(int[] array) {
if (array == null || array.length == 0) {
return new int;
}
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;
}
// 更新最大和及位置（优先选择长度更长的）
if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {
maxSum = currentSum;
start = i;
end = j;
}
}
}
// 构建结果数组
int[] result = new int;
System.arraycopy(array, start, result, 0, result.length);
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n³)，三重循环嵌套</li>
<li><strong>空间复杂度</strong>：O(1)，除结果外只使用常数空间</li>
</ul>
<h3 id="优化枚举法前缀和思想">优化枚举法（前缀和思想）</h3>
<p>在暴力法基础上优化，利用前缀和在计算子数组和时复用之前的结果，减少一层循环</p>
<pre><code class="language-java">public class Solution {
public int[] findMaxSubarray(int[] array) {
if (array == null || array.length == 0) {
return new int;
}
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; // 复用之前计算的结果
// 更新最大和（优先选择长度更长的）
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;
System.arraycopy(array, start, result, 0, result.length);
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，减少了一层循环</li>
<li><strong>空间复杂度</strong>：O(1)，常数级别空间复杂度</li>
</ul>
<h3 id="分治法递归思维">分治法（递归思维）</h3>
<p>采用分治思想，将问题分解为更小的子问题</p>
<p>将问题分解为左半部分、右半部分和跨越中间的三部分</p>
<p>即递归求解左右子数组，合并时处理跨越中间的情况</p>
<pre><code class="language-java">public class Solution {
public int[] findMaxSubarray(int[] array) {
if (array == null || array.length == 0) {
return new int;
}
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);
}
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;
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;
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;
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;
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n log n)，递归深度为log n，每层处理时间为O(n)</li>
<li><strong>空间复杂度</strong>：O(log n)，递归调用栈的深度</li>
</ul>
<h3 id="动态规划-kadane算法最优解">动态规划-Kadane算法（最优解）</h3>
<p>遍历数组，维护当前子数组和，根据规则重置或扩展当前子数组</p>
<p>假设现在有 n 个元素，突然加上⼀个元素，变成 n+1 个元素，对连续⼦数组的最⼤和有什么影响呢？</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251152683.png" alt="" loading="lazy"></p>
<p>我们只需要知道以每⼀个元素结尾的最⼤连续⼦数组，再维护⼀个最⼤的值即可。</p>
<p>假设数组为num[] ，⽤ dp 表示以下标 i 为终点的最⼤连续⼦数组和，遍历每⼀个新的元素nums ，以 num 为连续⼦数组的情况只有两种：</p>
<ul>
<li>dp + num</li>
<li>只有num</li>
</ul>
<p>所以以nums 结尾的最⼤连续⼦数组和为： dp = max( dp + num,num)</p>
<p>在计算的过程中，需要维护⼀个最⼤的值，并且把该连续⼦数组的左边界以及右边界维护好，最后根据维护的区间返回。</p>
<pre><code class="language-java">public class Solution85 {
public int[] FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int;
dp = array;
int maxsum = dp;
int left = 0, right = 0;
int maxLeft = 0, maxRight = 0;
for (int i = 1; i < array.length; i++) {
right++;
dp = Math.max(dp + array, array);
if (dp + array < array) {
left = right;
}
// 更新最⼤值以及更新最⼤和的⼦数组的边界
if (dp > maxsum || dp == maxsum && (right - left + 1) > (maxRight - maxLeft + 1)) {
maxsum = dp;
maxLeft = left;
maxRight = right;
}
}
// 保存结果
int[] res = new int;
for (int i = maxLeft, j = 0; i <= maxRight; i++, j++) {
res = array;
}
return res;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，单次遍历数组</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19559008
頁:
[1]