Maximum sum of suborders

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

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution one: dynamic programming

First, we initialize both Max and sum to the first element of nums, and then iterate through the array starting at bit 2:

  • whensum <= 0When,sumSet to the value of the current index, which is the value accumulated before discarding;
  • whensum > 0When,sumAdd the value of the current index bit, and add;
  • And then every convenient time Max is the greater of Max and sum.

Finally, return Max for the final result.

public class LeetCode_053 { public static int maxSubArray(int[] nums) { int max = nums[0], sum = nums[0]; for (int i = 1; i < nums.length; i++) { if (sum <= 0) { sum = nums[i]; } else { sum = sum + nums[i]; } max = Math.max(max, sum); } return max; } public static void main(String[] args) { int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(maxSubArray(nums)); }}

【 Daily Message 】
In a busy day, we should learn to find a reason to be happy every day, even if it is only because the sun is warm and the electricity is full.