Topic describes

This is the 53 largest suborder sum on LeetCode, and the difficulty is simple.

Key words: array, sum, dynamic programming

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Example 2:

Input: nums = [1] Output: 1Copy the code

Example 3:

Input: nums = [0] Output: 0Copy the code

Example 4:

Input: nums = [-1] Output: -1Copy the code

Example 5:

Input: nums = [-100000] Output: -100000Copy the code

Tip:

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

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

Violence law

If you do it by force, you go through the sequence in a double loop, you get the sum of all the suborders, you keep the maximum until you get the maximum sum.

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int ans = nums[0];
        // I is the starting position of the subsequence
        for (int i = 0; i < len; i++) {
            int sum = 0;
            // j is the end of the subsequence
            for (int j = i; j < len; j++) {
                // Calculate the sum of suborders, if large, record
                sum += nums[j];
                if(sum > ans) { ans = sum; }}}returnans; }}Copy the code

Dynamic programming

According to the above violent solution, we can find that in the process of summing, if the number to be added > 0, the result will increase (positive effect), and conversely decrease (negative effect).

When we iterate through the array to a certain coordinate, if the value is a number greater than 0, the maximum subsequence sum should be added to it, and vice versa, the maximum subsequence sum computed previously is compared to the current value.

Using dynamic programming to convert to the state transition equation is: dp[I] = Max (dp[i-1], nums[I])

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // Initializes the dynamic plan value and the result value
        int dp = nums[0];
        int ans = nums[0];
        for (int i = 1; i < len; i++) {
            // Compare the current value with (current value + the sum of the previous suborder)
            dp = Math.max(dp + nums[i], nums[i]);
            // Get the maximum suborder sum
            ans = Math.max(ans, dp);
        }
        returnans; }}Copy the code

reference

My Github repository has been set up synchronously, click access