package com.q0053;

import java.util.stream.IntStream;

/**

* @author xjn

* @since 2020-05-31

* https://leetcode-cn.com/problems/maximum-subarray/

* 53. 最大子序和

* 时间复杂度O(n)

* 空间复杂度O(n)

*/

public class Solution {

public int maxSubArray(int[] nums) {

//dp[i]:以nums[i]为结尾的最大子数组的和

//1.相连 dp[i] = dp[i-1] + nums[i]

//2. 不相连 dp[i] = nums[i]

if (nums == null) {

return 0;

}

if (nums.length == 1) {

return nums[0];

}

int[] dp = new int[nums.length];

for (int i = 0; i < dp.length; i++) {

dp[i] = nums[i];

}

for (int i = 1; i < nums.length; i++) {

dp[i] = Math.max(dp[i], dp[i - 1] + nums[i]);

}

return IntStream.of(dp).boxed().max(Integer::compareTo).get();

}

public static void main(String[] args) {

Solution solution = new Solution();

System.out.println(solution.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));

System.out.println(solution.maxSubArray(new int[]{-1, -2}));

}

}