连续子数组的最大和

标签：分治、DP

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

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

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

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

    package cekai;
    
    /**
     * @author: 86182
     * @description: 剑指 Offer 42. 连续子数组的最大和
     * @date: 2021/4/8 9:50
     */
    public class maxSubArray {
        public static void main(String[] args) {
            int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
            int res = func2(nums);
            System.out.println(res);
        }
    
        /**
        func()的代码中，申请了一个长度为len的数组，
        但在转移公式计算的时候，每次计算当前值的时候只会用到前面的那个值，
        再往前面就用不到了，这样实际上是造成了空间的浪费。
        这里不需要一个数组，只需要一个临时变量即可
         由于省去dp列表使用的额外空间，使得空间复杂度从 O(N)降至 O(1)
         */
        private static int func2(int[] nums) {
            int len = nums.length;
            int tmp = nums[0];
            int max = tmp;
            for (int i = 1; i < len; i++) {
                tmp = nums[i] + Math.max(tmp, 0);
                max = Math.max(max, tmp);
            }
            return max;
        }
    
        private static int func(int[] nums) {
            int len = nums.length;
            int[] dp = new int[len];
    
            dp[0] = nums[0];
            int max = dp[0];
            for (int i = 1; i < len; i++) {
                dp[i] = nums[i] + Math.max(dp[i - 1], 0);
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    
    }