剑指offer 42 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

动态规划

/**
 * DP
 *
 * @param nums
 * @return
 */
/* public static int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;

    int len = nums.length;
    // dp[i] 表示以nums[i]结尾的连续子数组的最大和
    int[] dp = new int[len];
    // 初始状态
    dp[0] = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < len; i++) {
        // 状态转换
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        maxSum = Math.max(dp[i], maxSum);
    }
    return maxSum;
}*/

动态规划+状态压缩

/**
 * DP ：状态压缩，不利用数组，将空间复杂度由O(n)变为O(1)
 *
 * @param nums
 * @return
 */
public static int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;

    int len = nums.length;
    // dp[i] 表示以nums[i]结尾的连续子数组的最大和
    int dp_0 = nums[0];        // dp_0表示初始状态
    int maxSum = nums[0];
    for (int i = 1; i < len; i++) {
        // 状态转换，dp_0先表示前一个状态，状态更新好再表示当前状态
        dp_0 = Math.max(dp_0 + nums[i], nums[i]);
        maxSum = Math.max(dp_0, maxSum);
    }
    return maxSum;
}

测试用例

public static void main(String[] args) {
    int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int ans = MaxSubArray.maxSubArray(nums);
    System.out.println("MaxSubArray demo01 result: " + ans);
}