最大子序列和（leetcode）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum;
        for(int i = 0;i < nums.size();i++){
            for(int j = i;j < nums.size();j++){
                sum = 0;//计算nums[i]到nums[j]
                for(int k = i;k <= j;k++){
                    sum = sum + nums[k];
                    if(maxSum < sum) maxSum = sum;
                }
            }
        }
        return maxSum;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum;
        for(int i = 0;i < nums.size();i++){
            sum = 0;
            for(int j = i;j < nums.size();j++){
                    sum = sum + nums[j];
                    if(maxSum < sum) maxSum = sum;
                }
            }
        return maxSum;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int arrSum = nums[0];
        for(int i = 1;i < nums.size();i++){
            arrSum = max(nums[i],arrSum + nums[i]);
            maxSum = max(maxSum, arrSum);
        }
        return maxSum;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int right = nums.size()-1;
        int left = 0;
        int result = maxSubArrayHelp(nums, left, right);
        return result;
    }
    int maxSubArrayHelp(vector<int>& nums,int left,int right){
        //递归中止条件
        if(left == right) return nums[left];

        //递归
        int mid = (left + right)/2;
        int leftsum = maxSubArrayHelp(nums, left, mid);
        int rightsum = maxSubArrayHelp(nums, mid+1, right);
        int midsum = maxSubArrayMid(nums, left, right, mid);

        //判断三者中的最大值
        int result = max(leftsum, rightsum);
        int z = max(result, midsum);

        return z;
    }

    int maxSubArrayMid(vector<int>& nums,int left, int right,int mid){
        int leftSum = INT_MIN;
        int sum = 0;

        //从mid开始向左的序列的最大值
        for(int i = mid;i >= left;i--){
            sum = sum + nums[i];
            leftSum = max(sum, leftSum);
        } 
        int rightSum = INT_MIN;
        sum = 0;
        //从mid向右的最大值
        for(int j = mid+1;j <= right;j++){
            sum = sum + nums[j];
            rightSum = max(sum, rightSum);
        }

        return rightSum + leftSum;
    }
};