1. The subject

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 continuous subarrays [4,-1,2,1] is 6.

Example 2:

Input: nums = [1]

Output: 1.

Example 3:

Input: nums = [0]

Output: 0

Example 4:

Input: nums = [-1]

Output: 1

Example 5:

Enter: nums = [-100000]

Output: – 100000

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.

2. The answer

Train of thought 1.

I haven’t met the problem that can be solved by violence for a long time, and my prehistorical power has been suppressed. Without saying anything else, I will directly solve the problem:

• Declare the actual maximum temporary variable
• Outer loop loop array that declares the maximum temporary variable in this loop

• The inner loop starts accumulating at the current position, and the larger one is replaced by the larger one compared to the current maximum, and the other continues
• At the end of the inner loop, compare the maximum value of this loop with the actual maximum value

• The outer loop continues to guide the end

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int tmpMax = nums[i];
            int sum = tmpMax;
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (tmpMax < sum) {
                    tmpMax = sum;
                }
            }
            max = Math.max(max, tmpMax);
        }
        returnmax; }}Copy the code

Time complexity

I’m using two loops, so it’s O(n ^ 2).

Spatial complexity

Constant O (1)

Submit the results

Idea 2 (Greed)

Try to see if the algorithm can be greedy:

1. The limiting value is a continuous array with a number less than n, and the expected value is the sum of the values of the continuous array.

2. Is it possible to use a greedy algorithm: iterate through the array and add the sum of array elements? If the sum of the subarray is negative after adding the current value (the current value cancels out the contribution of the subarray), then the contribution of the current value is negative, directly skip the current value and take the next value as the starting point.

3. Use examples [-2,1,-3,4,-1,2,1,-5,4] to try to find the optimal solution

The eldest order is: [4,-1,2,1], and is 6

public int maxSubArray(int[] nums) {
    int max = nums[0];
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum > max) {
            max = sum;
        }

        if (sum <= 0) {
            sum = 0;// Skip the current value and start counting from the next value}}return max;
}
Copy the code

Time complexity

I’m using a layer 1 loop, so O(n)

Spatial complexity

Constant O (1)

Submit the results

Dynamic programming is suitable for finding the optimal solution, but has not learned, and so learn to supplement