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
