面试经典 150 题-Kadane

LeetCode 面试经典 150 题-Kadane

最大子数组和

动态规划

1. 划分阶段：按子数组结尾的位置划分阶段。
2. 定义状态：dp[i]表示以nums[i]结尾的最大子数组和。
3. 状态转移方程：dp[i] = max(dp[i-1], 0) + nums[i]。
4. 初始条件：dp[0] = nums[0]。
5. 返回结果：维护一个最大和变量。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = dp[0];
        
        // 遍历数组
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], 0) + nums[i];
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

分治法

维护四个变量：

• lSum：以l为左端点的最大子段和，lSum要么等于左子区间的lSum，要么等于左子区间的iSum+右子区间的lSum，取较大值。
• rSum：以r为右端点的最大子段和，rSum要么等于右子区间的rSum，要么等于右子区间的iSum+左子区间的rSum，取较大值。
• mSum：[l,r]区间内的最大和，它要么等于左子区间的mSum，要么等于右子区间的mSum，要么横跨两区间，即左子区间的rSum + 右子区间的lSum，三者取较大值。
• iSum：[l,r]区间的和，等于左子区间的iSum + 右子区间iSum。

1. 用结构体定义线段树的这4个状态；
2. 定义线段树的pushup操作：即给定状态left和right，计算合并后的状态。
3. 定义获取子区间的和的函数：给定数组和左右下标，递归计算左右子区间状态，返回合并后的状态。
4. 返回结果：get(nums, 0, nums.size() - 1).mSum;

class Solution {
    // 定义状态
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return get(nums, 0, nums.length - 1).mSum;   
    }

    // 合并两个区间
    public Status pushUp(Status left, Status right) {
        int iSum = left.iSum + right.iSum;
        int lSum = Math.max(left.lSum, left.iSum + right.lSum);
        int rSum = Math.max(right.rSum, right.iSum + left.rSum);
        int mSum = Math.max(Math.max(left.mSum, right.mSum), left.rSum + right.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    // 获取区间和
    public Status get(int[] nums, int left, int right) {
        // 递归结束
        if (left == right) {
            return new Status(nums[left], nums[left], nums[left], nums[left]);
        }

        // 分治法求区间和
        int mid = (left + right) >> 1;
        Status lSub = get(nums, left, mid);
        Status rSub = get(nums, mid + 1, right);

        return pushUp(lSub, rSub);
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(logn)

环形子数组的最大和

Kadane

最大的环形子数组和 = max(最大子数组和，数组总和-最小子数组和)。如果数组的所有数都是负数，第一种情况sum会等于数组中的最大值，而对二种情况sum=0（最小的子数组就是本数组，total-total=0）。所以多加一个case，判断最大子数组和是否小于0，小于0，直接返回该maxSubArray。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0, maxSum = nums[0], curMax = 0, minSum = nums[0], curMin = 0;
        for (int x : nums) {
            curMax = Math.max(curMax + x, x);   // 继续子数组or重新开始子数组
            maxSum = Math.max(curMax, maxSum);  // 更新全局最大子数组和
            curMin = Math.min(curMin + x, x);   // 继续子数组or重新开始子数组
            minSum = Math.min(curMin, minSum);  // 更新全局最小子数组和
            total += x;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

总结

Kadane 算法（Kadane’s algorithm）是一种用于解决最大子数组问题的动态规划算法。最大子数组问题的目标是在一个整数数组中找到一个连续的子数组，使得该子数组的和最大。

Kadane 算法的思路很简单：从头到尾遍历数组，用两个变量maxSum和curMax分别记录全局最大子数组的和以及当前最大子数组的和，每次遍历更新这两个变量即可。