This is the 21st day of my participation in the August Text Challenge.More challenges in August

152. Maximum subarray of product

Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.

Example 1:

Input: [2,3,-2,4] output: 6 explanation: the subarray [2,3] has a maximum product of 6. Example 2:

Input: [- 2, 0, 1] output: 0 explanation: the result can’t to 2, because [2, 1] is not an array.

Their thinking

The variation problem of the maximum suborder sum, because negative and negative make a positive, and negative can also be multiplied by a maximum, so we also need to maintain a minimum.

code

class Solution {
    public int maxProduct(int[] nums) {

        int max=nums[0],min=nums[0],res=nums[0];
        for (int i = 1; i < nums.length; i++) {
            int pm=max;
            max= Math.max(Math.max(nums[i],max*nums[i]),min*nums[i]);
            min= Math.min(Math.min(nums[i],min*nums[i]),pm*nums[i]);
            res=Math.max(max,res);
        }
        returnres; }}Copy the code

  • Time complexity: The program iterates through NUMS once, so the progressive time complexity is O(n).

  • Space complexity: after optimization, only constant temporary variables are used as auxiliary space, which has nothing to do with N, so the complexity of progressive space is O(1).

21. Reorder the array so that the odd number precedes the even number

Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the second half.

Example:

Input: nums = [1,2,3,4] output: [1,3,2,4] note: [3,1,2,4] is also one of the correct answers.

Tip:

0 <= nums.length <= 50000 1 <= nums[i] <= 10000

Their thinking

It comes from the idea of quicksort, which allows you to divide less than the central value and more than the central value on both sides of an array

And we can use the same idea, to arrange the odd and even numbers on both sides

code

class Solution {
    public int[] exchange(int[] nums) {

        int l=0,n=nums.length,r=n-1;
        while (l<r)
        {
            while (l<r&&nums[l]%2= =1)
                l++;
            while (l<r&&nums[r]%2= =0)
                r--;
            int t=nums[r];
            nums[r]=nums[l];
            nums[l]=t;
        }
        returnnums; }}Copy the code