牛客算法-第二章

1.求两个子数组最大的累加和
【题目】
给定一个数组，其中当然有很多的子数组，在所有两个子数组的组合中，找到相
加和最大的一组，要求两个子数组无重合的部分。最后返回累加和。
【要求】
时间复杂度达到 O(N)

总结，首先提炼算法原型，就是求解一个数组，数组元素包括正负整数，求取最大子数组和（子数组是连续的）。

那么如何求解呢？很简单，从左往右遍历，一个cur变量，一个max变量，cur初始化为arr[0].
cur=max(0,cur),保证cur的数值大于等于0；
cur+=arr[i];
max=max(max,cur);
利用cur更新max，最终返回max就是结果：最大子数组和。

回归本道题，求解两个子数组的最大累加和，如何算呢？
而且还要求不相容。什么是两个不相容的子数组，其实就是位置不相容，不能有重叠的数据。（注意，此处不是数字不能重复！！）。如果改成两个可以相容的不同子数组，又如何计算呢？很显然，求出最大子数组和，以及次大子数组和，进行累加，就可以得出了。那么本题又该如何计算呢？

0....  i .....n-1
如上举例，当前遍历到i，我们可以根据以上的算法原型求解出0~i的最大子数组和，也可以求出i+1~n-1的最大子数组和。
就是求出了以i为界限的左右两边的子数组和。遍历数组中所有的位置，可以得到一个集合u,而本题的答案显然就在其中，集合中的最大值，就是本题的戒了。

算法思想就是上面的。为了在O(n)的时间内解决这道题，也就是要求我们遍历的过程中得出答案，所以分别求解左右两边的最大子数组和就必须用两个辅助数组lmax[]和rmax[]来实现。

lmax[]就从0~n-1从左到右遍历得出；
对应的，rmax[]就从n-1~0从右到左遍历得出。

当然，这里遍历的过程就是从左到右的方式，所以其实lmax[]是可以省略的。在遍历的过程中也可以进行求解。

总结，针对子数组问题，要养成假想以i结尾的子数组的情况，然后就是规律题了。

2.未排序正数数组中累加和为给定值的最长子数组长度
【题目】
给定一个数组 arr，该数组无序，但每个值均为正数，再给定一个正数 k。求 arr
的所有子数组中所有元素相加和为 k 的最长子数组长度。
例如，arr=[1,2,1,1,1]，k=3。
累加和为 3 的最长子数组为[1,1,1]，所以结果返回 3。
【要求】
时间复杂度 O(N)，额外空间复杂度 O(1)



针对这一题，采用的算法，归纳就是使用双指针L，R。

举例：
    2 3 1 1 1 1 1 3 2
    假设k=5；
    开始的时候，sum=0;
    还有一个记录长度的变量len=0;
    L,R都初始化为最左边。
    if(sum<=k)
    {
        R++;
    }
    else
    {
        L++;    
    }


    此外，当sum==5的时候，记得更新len的值，如何更新呢？len=R-L+1;

int left=0;
int right=0;
int sum=arr[0];
int len=0;

while(right < arr.length) 
{
    if(sum==k)
    {
        len=Math.max(len,right-left+1);
        sum-=arr[left++];

    }else if(sum<k)
    {
        right++;
        if(right== arr.length)
        {
            break;

        }
        sum+=arr[right];

    }
    else
    {
        sum-=arr[left++];
    }




}

3.未排序数组中累加和为给定值的最长子数组系列问题
【题目】
给定一个无序数组 arr，其中元素可正、可负、可 0，给定一个整数 k。求 arr
所有的子数组中累加和为 k 的最长子数组长度。
【补充题目】
给定一个无序数组 arr，其中元素可正、可负、可 0。求 arr 所有的子数组中正
数与负数个数相等的最长子数组长度。
【补充题目】
给定一个无序数组 arr，其中元素只是 1 或 0。求 arr 所有的子数组中 0 和 1 个
数相等的最长子数组长度。
【要求】
时间复杂度 O(N)

总结，算法要点如下

如果一个数组，sum[i]+k=sum[j]
也就说明[i+1 ~j]之间的和为k。

如何求解呢？举例，sum[j]=10,k=6,所以我们就是求解第一个出现子数组和为4的位置，就是sum[i].

举例：
4 -2 1 1 1 3
下标：0 1 2 3 4 5
设定k=5.

首先弄一个哈希表map，存放第一个出现子数组和为0.。1.。。等等总之是未出现过的数，对应的键就是这个第一次出现的子数组和，对应的值，就是第一次出现这个键的下标值。但是这里还有一个重要的注意点，需要提前将（0,-1）插入map中。
这是为什么呢？因为之前我们的设定是从i+1开始，这样我们就根本不可能求出从0开始的了，所以我们增加一个从-1开始的情况，但是又因为他是虚无的，所以他是0.

总之，就是为了保持整个逻辑的完备性，就好像添加了一个head指针的用途一样。

那么，如何求解补充题目1呢？
题目可以遍历一遍，然后将数组中正数变为1，负数变为-1，0还是0。所以问题就是求arr中子数组和为0的最大长度。也就是这里k=0了。

那么，如何求解补充题目2呢？
题目遍历一遍，然后将数组中的1不动，还是1,0变为-1,。所以问题依然变成了，求解arr数组中子数组为0的最大子数组长度。同样是k=0；

总之，就是这个套路。