LeetCode每日一题环形子数组的最大和 （中等）

调查动态规划,要点关注动态规划思想和代码完成。

       total += nums[i]
        currMax = max(currMax+nums[i], nums[i])
        maxSum  = max(maxSum, currMax)

标题描绘：

给定一个长度为 n 的环形整数数组 nums ，回来 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的结尾将会与最初相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i – 1 + n) % n] 。

子数组 最多只能包括固定缓冲区 nums 中的每个元素一次。形式上，关于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其间 k1 % n == k2 % n 。

示例

• 示例 1：

输入：nums = [1,-2,3,-2] 输出：3 解说：从子数组 [3] 得到最大和 3

• 示例 2：

输入：nums = [5,-3,5] 输出：10 解说：从子数组 [5,5] 得到最大和 5 + 5 = 10

• 示例 3：

输入：nums = [3,-2,2,-3] 输出：3 解说：从子数组 [3] 和 [3,-2,2] 都能够得到最大和 3

解题思路

最开端的时分，思路：遍历num数组，获取最大的数，从此数开端。然后向左右俩边辐射，若是正数，直接相加。若是负数，则持续向左右俩边遍历。 然后代码写如下

func maxSubarraySumCircular(nums []int) int {
    max := 0
    index := 0
    leng := len(nums)
    for i:=0 ; i < leng ; i++{
        if max < nums[i]{
            max = nums[i]
            index := i
        }
    }//找最大值，以及其所对应得下标
    if nums[(index+1)%n] >0 {
        max = max+ nums[(index+1)%n]
    }
    if nums[(index-1)%n] >0 {
        max = max+ nums[(index-1)%n]
    }//左右俩边大于0 ，就将其加入max中
    //假如小于0，也不能直接舍弃，还要判别该负数的下一个是不是正数且大于该负数的绝对值。
    //有个问题，如是不是应该悉数用循环来遍历整个数组。
    //不能这么做了，由于你不知道究竟是不是满足大于0,。
    //要不运用昨天的方法，
    if nums[(index+1)%n] <=0 {
        for k := 0 ; k < leng -1 ;k++{
            k = (k+ index +1)%n//这个是负数的下标
        }
    }
}

很明显，由于你不确定究竟后续还能不能取得一个大于0的数，所以这种方法肯定不能够。

然后换一种方法，能不能像昨天的标题一样，将数组中的每个数都差一个下标。然后进行排序。

假如这样做，思路便是：先将其从大到小排序？（坏，如同不一定从大的数开端便是正确的 ，比方 -7 7 -8 -9 1 2 -7这样，明显不能把-7包进去）

所以说，唔，仍是先按从大到小排。然后读榜首个数的时分，将其左右两边的数同加直到碰到下一个正数，

官方回答 （动态规划）

这题一共有两种状况 下面的这个子数组指最大和的子数组

榜首种状况：这个子数组不是环状的，便是说首尾不相连。

第二种状况：这个子数组一部分在首部，一部分在尾部，咱们能够将这第二种状况转换成榜首种状况

如下图：

所以这最大的环形子数组和 = max(最大子数组和，数组总和-最小子数组和)

证明

证明一下第二种状况（最大子数组是环形的）

max(前缀数组+后缀数组)

= max(数组总和 – subarray) subarray指的是前缀数组和后缀数组中心的数组

= 数组总和 + max(-subarray) 数组总和是不变的，直接提出来

= 数组总和 – min(subarry) 。。。这个都懂吧，把负号提出来，max变成min

极端状况：假如说这数组的所稀有都是负数，那么上面的公式还需求变一下，由于这种状况，关于上面的榜首种状况sum会等于数组中的最大值，而对二种状况sum=0（最小的子数组便是本数组，total-total=0）。所以多加一个case，判别最大子数组和是否小于0，小于0，直接回来该maxSubArray

代码如下：

func maxSubarraySumCircular(nums []int) int {
    total, maxSum, minSum, currMax, currMin := nums[0], nums[0], nums[0], nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        total += nums[i]
        currMax = max(currMax+nums[i], nums[i])
        maxSum  = max(maxSum, currMax)
        currMin = min(currMin+nums[i], nums[i])
        minSum  = min(minSum, currMin)
    }
    //等价于if maxSum < 0
    if total == minSum  {
        return maxSum
    } else {
        return max(maxSum, total - minSum)
    }
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
作者：xing-you-ji
链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/solution/wo-hua-yi-bian-jiu-kan-dong-de-ti-jie-ni-892u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者取得授权，非商业转载请注明出处。

代码解说

    for i := 1; i < len(nums); i++ {
        total += nums[i]
        currMax = max(currMax+nums[i], nums[i])
        maxSum  = max(maxSum, currMax)
        currMin = min(currMin+nums[i], nums[i])
        minSum  = min(minSum, currMin)
    }

这段代码是运用Go语言编写的用于查找一个整数数组nums中的最大子数组和和最小子数组和的算法。代码运用了动态规划的思想来逐渐更新当时的最大子数组和maxSum、当时的最小子数组和minSum、当时最大子数组和的累加值currMax和当时最小子数组和的累加值currMin。

（这一块代码是核心，动态规划来更新大小，假如我写的话，应该不会关注min的取值，只会写前三行，也便是我考虑的第二种状况是把他当成榜首种状况相同，前面证明的变形太细了！）

if total == minSum

这是一个条件判别句子，用于查看数组的总和total是否等于最小子数组和minSum。 假如数组的总和等于最小子数组和，那么这意味着数组中的所有元素都是非正数（负数或零）， 由于minSum是最小子数组和，而total是整个数组的总和。在这种状况下，数组中没有正数，由于假如有正数，将其加入到子数组和中，将会使得子数组和变得更大，而这与minSum持平是矛盾的。

LeetCode面试经典150题第4题：删去有序数组中的重复项 II（中等）

标题描绘：

给你一个有序数组 nums ，请你 原地 删去重复呈现的元素，使得呈现次数超越两次的元素只呈现两次 ，回来删去后数组的新长度。

不要运用额定的数组空间，你必须在 原地 修改输入数组 并在运用 O(1) 额定空间的条件下完成。

示例

• 示例 1：

输入：nums = [1,1,1,2,2,3] 输出：5, nums = [1,1,2,2,3] 解说：函数应回来新长度 length = 5, 而且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需求考虑数组中超出新长度后面的元素。

• 示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3] 输出：7, nums = [0,0,1,1,2,3,3] 解说：函数应回来新长度 length = 7, 而且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需求考虑数组中超出新长度后面的元素

解题思路

由于此题数组内已经按大小排序了，所以只需求建立一个检测量signal，然后去判别重复数是否超越2个即可。 仅有需求留意的点是，不能新建一个数组去存储，而是要在原有的数组上进行操作！

没有啥需求留意的，感觉像简单难度。 代码如下：

//此题数组内已经按大小排序了，所以只需求建立一个检测量signal=2，然后去判别重复数是否超越2个
func removeDuplicates(nums []int) int {
    leng := len(nums)
    signal := 1 
    j :=2 
    for i:=2 ; i< len(nums) ; i++{
        if nums[i] == nums[j-1] && nums[i]==nums[j-2]{
            signal =0
        }
        if signal ==0{
            leng--
        }else{
            nums[j]= nums[i]
            j++
        }
        signal = 1
    }
    return leng
}

我的解法，其实运用于较小位，假如保存k位，且k很大，我肯定不能罗列完。

官方回答（双指针）

通用解法

为了让解法更具有一般性，咱们将原问题的「保存 2 位」修改为「保存 k 位」。

由于给定数组是有序的，所以相同元素必定接连。咱们能够运用双指针处理本题，遍历数组查看每一个元素是否应该被保存，假如应该被保存，就将其移动到指定方位。

详细地，咱们界说两个指针 slow 和 fast 分别为慢指针和快指针，其间慢指针表示处理出的数组的长度，快指针表示已经查看过的数组的长度，即 nums[fast] 表示待查看的榜首个元素，nums[slow−1] 为上一个应该被保存的元素所移动到的指定方位。

由于本题要求相同元素最多呈现两次而非一次，所以咱们需求查看上上个应该被保存的元素 nums[slow−2] 是否和当时待查看元素 nums[fast] 相同。当且仅当 nums[slow−2]=nums[fast] 时，当时待查看元素nums[fast] 不该该被保存（由于此时必定有 nums[slow−2]=nums[slow−1]=nums[fast]）。最终，slow即为处理好的数组的长度。

特别地，数组的前两个数必定能够被保存，因此关于长度不超越 2 的数组，咱们无需进行任何处理，关于长度超越 2的数组，咱们直接将双指针的初始值设为 2 即可。

假如是保存k位nums[slow-2] != nums[fast]将2改为k即可。一起初值也跟着改。

func removeDuplicates(nums []int) int {
    n := len(nums)
    if n <= 2 {
        return n
    }
    slow, fast := 2, 2
    for fast < n {
        if nums[slow-2] != nums[fast] {
            nums[slow] = nums[fast]
            slow++
        }
        fast++
    }
    return slow
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-yec2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者取得授权，非商业转载请注明出处。

唔，仍是写复杂了很多，悲

正反向代理

docker建立haproxy 四层代理，一起3个后端web服务器，露出8000端口，做负载均衡，后端服务器采用RR的方式，恣意一个Sever挂掉，不影响8000端口宿主机的访问

1.创建一个 Docker Compose 文件来界说 HAProxy 和三个后端 Web 服务器容器。咱们将运用 Docker Hub 中的 haproxy 映像和 nginx 等简单 Web 服务器的三个实例来进行演示。docker-compose文件如下

services:
haproxy:  
image:haproxy:latest  
ports:  
-"8000:8000"  
volumes:  
-./haproxy.cfg:/usr/local/etc/haproxy/haproxy.cfg  
networks:  
-proxy_network  
backend1:  
image:python:3  
command:python-mhttp.server80  
networks:  
-proxy_network  
backend2:  
image:python:3  
command:python-mhttp.server80  
networks:  
-proxy_network  
backend3:  
image:python:3  
command:python-mhttp.server80  
networks:  
-proxy_network  
networks:  
proxy_network:

2.haproxy.cfg如下

daemon
maxconn256  
defaults  
modetcp  
timeoutconnect5000ms  
timeoutclient50000ms  
timeoutserver50000ms  
frontendhttp-in  
bind*:8000  
default_backendbackend_servers  
backendbackend_servers  
modetcp  
balanceroundrobin  
serverbackend1backend1:80check  
serverbackend2backend2:80check  
serverbackend3backend3:80check