2022最大和打卡

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
环形子数组的最大和

给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i],C[i+1], ..., C[j]，不存在 i <= k1,k2 <= j 其中 k1 % A.length = k2 % A.length）
乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
乘积为正数的最长子数组长度

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。请你返回乘积为正数的最长子数组长度。

最大子数组和

思路

针对连续数组的最大和而言，直观的想就是累加求和取最值的过程，如果数组所有的元素均是自然数，那么就是整个数组元素累加求和，如果元素中含有负数那么当前元素的最大和依赖于前一个元素的最大和，如果前一个元素的最大和是正数则累加，如果是负数，那么则比较前一个元素最大和和当前元素的大小

代码

func maxSubArray(nums []int) int {
    sum:=nums[0]
    for i:=1;i<len(nums);i++{
        nums[i]=max(nums[i-1],0)+nums[i]
        sum=max(sum, nums[i])
    }
    return sum
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

环形子数组的最大和

思路

环形数组计算最大和第一种情况来看当整个数组都是自然数那么最大和就是整个元素的总和。如果含有负数，当负数在两边。那么就相当于绕圈了把整个环形数组展开可以理解为抛去负数的剩下数的最大和直接服用最大子数组和即可。如果含有负数，当负数在中间。就等于所有元素的和减去最小元素和就是整个数组的最大和

如图所示的数组要计算最大和

代码

func maxSubarraySumCircular(nums []int) int {
    maxSum,arrSum,minSum,tMax,tMin:=nums[0],0,nums[0],0,0
    for i:=0;i<len(nums);i++{
	arrSum+=nums[i]
    	tMax,tMin=max(tMax+nums[i],nums[i]),min(tMin+nums[i],nums[i])
    	maxSum=max(maxSum,tMax)
	minSum=min(minSum, tMin)
    }
    if maxSum<0{
	return maxSum
    }
    return max(maxSum,arrSum-minSum)
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

乘积最大子数组

思路

如图所示的数组要求这数组中子数组乘积最大的是多少，要想知道到当前元素的最大乘积就等于前一个元素的最大乘积值和当前元素的乘积和前一个元素的最小乘积和当前元素的乘积和当前元素的值 反过来要想知道到当前元素的最小乘积就等于 前一个元素的最小乘积值和当前元素的乘积和前一个元素的最大乘积和当前元素的乘积和当前元素的值 所以得出状态转移方程

代码

func maxProduct(nums []int) int {
    max,min,ans:=nums[0],nums[0],nums[0]
    for i:=1;i<len(nums);i++{
            mx:=max
            mn:=min
            max=Mathmax(mx*nums[i],Mathmax(nums[i],mn*nums[i]))
            min=Mathmin(mn*nums[i],Mathmin(nums[i],mx*nums[i]))
        
        ans=Mathmax(ans,max)
    }
    return ans
}
func Mathmax(a,b int)int{
    if a>b {
        return a
    }
    return b
}
func Mathmin(a,b int)int{
    if a<b {
        return a
    }
    return b
}

乘积为正数的最长子数组长度

思路

还是使用老图，懒得画图了，分析上述数组，乘积为正数的长度。如果当前元素是正数，正数长度加一，如果当前值是负数，正负长度累加交换如果当前元素是零，那么正负长度归零，在每次遍历的时候比较最大的正数长度就是到当前元素乘积为正数的最大长度的值。定义两个遍历P,N来用于统计正数乘积和负数乘积的长度，V代表当前元素.P(i-1),N(i-1)分别代表前一个正数乘积和负数乘积的长度。

代码

func getMaxLen(nums []int) int {
    p,n:=0,0
    if nums[0]>0{
        p=1
    }
    if nums[0]<0{
        n=1
    }
    ans:=p
    for i:=1;i<len(nums);i++{
        if nums[i]>0{
            p++
            if n>0{
                n++
            }else{
                n=0
            }
        }else if nums[i]<0{
            a,b:=p+1,0
            if n>0{
                b=n+1
            }
            p,n=b,a
        }else{
            p,n=0,0
        }
       ans=MathMax(ans,p) 
    }
    return ans    
}
func MathMax(a,b int)int{
    if a>b {
        return a
    }
    return b
}