41. 最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例：
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
要求时间复杂度为O(n)
想了一会并没有特别好的方法，想了一个用双指针的方法，通过了大部分的数据测试，但是还是有不通过的，我也不知道错在哪里，待会贴在下面，先说正确的方法。
思路
先分析下这个问题啊，主要有三种情况：
*1. 全部是负数，这就简单了，找到最大的负数就可以了。
*2. 全部是正数，也很简单，应该是把所有的数加起来就可以了。
*3. 有正也有负，最大子数组肯定是正的。
基于这三种情况分析，我们可以采用这样的思路，先设置一个max，把这个数设置为INT_MIN，设置sum作为变量来记录当前得到的字数组的和，一旦sum>max，就可以更新max，这样就能保证max是最大字数组的和，那么字数组如何更新呢，前面说了，如果有正数的话，最后的结果肯定是正的，那么我们遍历数组，把sum先初始化为第一个数，然后，从第二个数开始，如果发现前面的sum是负的，那么就可以把前面的字数组抛弃掉了，以当前的这个数作为新的字数组的起点，如果发现是正的，当前的这个数加入子数组，以此类推，这样就能找到最大字数组了。（每一次遍历的最后更新max）。
这样说来不是很直观，我们可以注意这样一个事实：我们要找的子数组的前面的几个数（不管是几个），和肯定不能是负的，如果是负的，那么去掉岂不是得到的和更大，这样就能理解为什么一旦发现前面的字数组为负的话，就丢掉，如果全负的话这种方式也是适合的，因为每次都会舍弃，sum的值就是当前元素，每次更新max，这样得到的max就是最大的那个元素。
这样的话代码也是很简洁了：

  int maxSubArray(vector<int> nums) {  
        if(nums.size()<=0){  
            return 0;  
        }   
        int max=INT_MIN,cur=0;     //c++最小值  
        for(int i=0; i<nums.size(); i++)    
        {    
            if(cur < 0)  
                cur = nums[i];  //如果前面加起来的和小于0，抛弃前面的  
            else  
                cur+=nums[i];  
  
            if(cur > max)  
                max = cur;  
        }    
        return max;    
          
    }  

我一开始想的另一种思路是：我把所有的数都先加起来，得到sum，然后用两个指针分别指向首尾，比较首尾元素的大小，总是把小的剔除掉（这样得到子数组和更大一些），字数组的和用sum减去剔除掉的数就可以了，如果两个数一样大，剔除掉任意一个就可以了（不能同时剔除两个‘比如[-1,-3,-1]'，如果同时剔除两个1，得到的最大值可能是-3，实际上是-1，但是同时被剔除掉了），我是用这个方法试了一些数据，感觉还挺靠谱，于是写了一下，中间用迭代器的程序还不对，最后该用下标才对，也没有找到错误在哪里，这个程序还通过了70%的测试数据，最后还是没有对，目前还没有找到问题在哪，代码就贴在下面了,如果有人看到（应该没有），发现问题在哪，还望告知！

int maxSubArray(vector<int> &nums) {
        auto beg=nums.begin();
        auto end=nums.end()-1;
        int res_max=accumulate(nums.begin(),nums.end(),0);   //先把所有数求和
        int sum_num=res_max;
        while(beg!=end)
        {
            if(*beg<*end)
            {
              sum_num-=(*beg);
              beg++;
              if(sum_num>res_max)
              res_max=sum_num;
            }
            if(*beg>*end)
            {
                sum_num-=(*end);
                end--;
                if(sum_num>res_max)
                res_max=sum_num;
            }
            if(*beg==*end)
            {
                sum_num-=(*beg);
                beg++;
                sum_num-=(*end);
                end--;
                if(sum_num>res_max)
                res_max=sum_num;
            }
        }
        return res_max;
        // write your code here
    } 
    */
    
    
    int maxSubArray(vector<int> &nums) {
    int beg = 0;
    int end = nums.size() - 1;
    int res_max = accumulate(nums.begin(), nums.end(), 0);   //先把所有树求和
    int sum_num = res_max;
    while (beg<end)
    {
        cout << beg << "  " << end << endl;
        if (nums[beg]<nums[end])
        {
            sum_num -= (nums[beg]);
            beg++;
            if (sum_num>res_max)
                res_max = sum_num;
        }
        if (nums[beg]>nums[end])
        {
            sum_num -= (nums[end]);
            end--;
            if (sum_num>res_max)
                res_max = sum_num;
        }
        if (nums[beg] == nums[end])
        {
            sum_num -= (nums[beg]);
            beg++;
            sum_num -= (nums[end]);
            end--;
        }
    }
    return res_max;
    // write your code here
    }

---

振哥指导了一个思路说是当两端相同的话，任意去掉一个是不明智的，后来我想了一下确实是这样的，因为如果恰好有一个就是最大子数组之列又恰好被去掉呢，比如现在得到一个[2,-1,5,-3,2]，最大字数组应该是[2,-1,5],但是我们这时候恰好把前面的2给去掉呢，这样得到的最大子数组只能是[5]了，这样显然是有问题的，嗯就是这样的。振哥英明。
one more question
我发现有个问题是一直被我忽略的，有时候在循环里写三个互斥的条件时，我很喜欢用三个if，就像这样：

while(--)
{
  if(--)  ---;
  if(--)  ---;
  if(--)  ---;
}

这样的写法有时候是很危险的，比如第一个if改变了第二个if里需要判断的某个值的话，这样就极有可能出错。而我们希望每次循环都只进入一个if，这里的三个if是分支结构，这个时候最好加上if，让逻辑更清晰一些：

while(--)
{
  if(--)  ---;
 else  if(--)  ---;
 else  if(--)  ---;
}

一般这种双指针的题，倒是可以用三个if，可能还效率高一些，因为即使第一个if里面出现了移动指针的情况，如果满足第二个if的话还是可以去移动指针的，因为即使这里用的是分支结构，通过while之后还是会进入倒第二个if里，但是为了保证逻辑上的正确，在判断的时候一定要记得着啦ing中结构的区别。