Leetcode – Sword finger Offer 42- maximum sum of contiguous subarrays

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

Enter an array of integers. One or more integers form a subarray. Find the maximum sum of all subarrays. The time complexity is O(n). 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. 1 <= arr. Length <= 10^ 5-100 <= arr[I] <= 100 https://leetcode-cn.com/problems/maximum-subarray/ Related Topics Array divide-and-conquer dynamic planning 👍 313 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: prefix and + violence method

  • sum[j]-sum[i-1] = a[i]+… +a[j]
  • The TLE
public int maxSubArray(int[] nums) {
            int[] sums = new int[nums.length + 1];
            int sum = 0,max =Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                sums[i + 1] = sum;
            }
            for (int i = 1; i < sums.length; i++) {
                for (int j = i; j < sums.length; j++) {
                    max = Math.max(sums[j] - sums[i-1],max);
                }
            }
            return max;
​
        }
Copy the code

Time complexity O(n2n^{2}n2)

Idea 2: One-dimensional dynamic programming

  • First, you can decide on a DP idea

  • Dp [I] represents the sum of the largest child elements ending in the ith element

  • Max (dp[I]+ nums[I], nums[I])

  • Otherwise, dp[I] = dp[i-1]

    public int maxSubArray(int[] nums) {
                int[] dp = new int[nums.length + 1];
                int ans = nums[0];
                dp[1] = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    // represents the sum of the largest child elements before i-1 and the sum of elements bounded to the current position
                    dp[i + 1] = Math.max(dp[i] + nums[i], nums[i]);
                    ans = Math.max(ans, dp[i + 1]);
                }
                return ans;
            }

Copy the code

Time complexity O(n)

Idea 3: Scroll through an array

  • According to the above dp equation, it can be found that the current evaluation is only related to one element above the sum of the current elements
  • So you can use scrolling arrays for optimization
    public int maxSubArray(int[] nums) {
                int ans = nums[0], pre = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    // represents the sum of the largest child elements before i-1 and the sum of elements bounded to the current position
                    pre = Math.max(pre+ nums[i], nums[i]);
                    ans = Math.max(ans, pre);
                }
                return ans;
            }
Copy the code

Time complexity O(n)

Line segment tree + divide and conquer This line segment tree + divide and conquer