[leetcode refers to offer 42. Maximum sum of continuous subarrays (simple)]

subject ：

Enter an integer array , One or more consecutive integers in an array form a subarray . Find the maximum sum of all subarrays .

The required time complexity is O(n).

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.

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The problem solving process ：

Dynamic programming Divide and conquer method

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int dp[] = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i=1;i<nums.length;i++){
    
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

Execution results ：