Three line code solution - Maximum sub segment and - DP

         Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray  [4,-1,2,1] And the biggest , by  6 .
Example 2：

Input ：nums = [1]
Output ：1
Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23
 

Tips ：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximum-subarray
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Write down the solution , The first n The maximum sum of terms is equal to n Xiangjiadi n-1 Item maximum and .

In layman's terms ：

        Let's nums = [-2,1,-3,4,-1,2,1,-5,4] As a sub problem ：

                The first sub question ： The maximum value of the first term max(nums[0])

                The second sub problem ： The maximum value from the first term to the second term is max(nums[0])+nums[1]

                ........

                The first n The sub problem of ： From item one to item two n The maximum value of the item max(nums[n-1])+nums[n]

        We can know , If n-1 Item maximum is greater than zero , that max(nums[n-1])+nums[n] It is bound to be greater than nums[n]

         Empathy , If n-1 The maximum value of the item is less than or equal to zero , that max(nums[n-1])+nums[n] Must be less than or equal to nums[n]

        So we can deduce an equation ：

                max_nums[n] = max_muns[n-1]+nums[n]        if(max_muns[n-1]>0)

                                          nums[n]                                  if(max_muns[n-1]<=0)

        We just need to compare max and nums[n], Assign a large value to max that will do

I wrote it on the Internet java Code .

Here is AC Code

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for(int i = 1;i<nums.length;i++){
            nums[i] = nums[i-1]>0?nums[i]+nums[i-1]:nums[i];
            max = nums[i]>max?nums[i]:max; 
        }
        return max;
    }
}