Topic:

  • 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 explanation: the maximum sum of consecutive subarrays [4,-1,2,1] is 6.

  • Notice that suborders are ordered.

Solution logic

  • Iteratively fetch each element num[I]
  • Sum (num[I]+sum);
  • If the value of sum is greater than that of result, update result with sum.

In the code


class Solution {
    public int maxSubArray(int[] nums) {
        int length ;
        if(nums==null||(length=nums.length)==0) {return 0;
        }

        int result = nums[0];
        // take the 0th position
        int sum = nums[0];
        for(int i = 1; i<length; i++){Ssum = nums[I]; ssum = nums[I];
            // At this time, we will make a comparison. Between the two, choose the largest piece. With the aid of Math. Max ();
            sum = Math.max(nums[i],sum+nums[i]);

            if(sum>result){ result = sum; }}returnresult; }}Copy the code

ps

  • The level of this problem in Leetcode is easy. If you don’t think carefully, you really can’t solve it. Impose practice even if you think you can

todo

  1. And so on review dynamic programming, with DP answer, I think there is a door;
  2. So review sliding window, using sliding window solution, I think there is a play;