求连续子序列最大和

给定一个无序数组，求最大的连续子数组的和

解法一：

• 思路：暴力解法，最大序列肯定以数组中某个数为起点，则依次遍历以每个点为起点的情况
• 时间复杂度：O(n平方)

int maxSubSequence1(vector<int> A, int n) {
    int max = INT_MIN;
    for (int i = 0; i < n; i++) {
        int tempSum = 0;
        for (int j = i; j < n; j++) {
            tempSum += A[j];
            max = tempSum > max ? tempSum : max;
        }
    }
    return max;
}

解法二：

• 思路：分治思想，结果有三种情况：

  • 情况1：最大子序列在左边部分
  • 情况2：最大子序列在右边部分
  • 情况3：最大子序列横跨左右两个部分

  然后每次递归过程都返回三者最大即可

• 时间复杂度：O(nlogn)

int maxForThree(int A, int B, int C) {
    if (A >= B && A >= C) {
        return A;
    }
    return maxForThree(B, C, A);
}

int maxSubSequence2(vector<int> A, int left, int right) {
    if (left == right) {
        return A[left];
    }

    int middle = left + (right - left)/2;
    
    // 左半部分
    int leftSum = 0;
    int leftMax = INT_MIN;
    for (int i = middle; i >= 0; i--) {
        leftSum += A[i];
        leftMax = leftSum > leftMax ? leftSum : leftMax;
    }
    
    // 右半部分
    int rightSum = 0;
    int rightMax = INT_MIN;
    for (int i = middle + 1; i < A.size(); i++) {
        rightSum += A[i];
        rightMax = rightSum > rightMax ? rightSum : rightMax;
    }
    
    return maxForThree(leftMax + rightMax, maxSubSequence2(A, left, middle), maxSubSequence2(A, middle + 1, right));
}

解法三：

• 思路：调整思考角度，暴力解法核心是最大子序列一定是以数组中某个数为起点，转变思维，最大子序列也一定是以数组中某个数为终点
• 时间复杂度：O(n)

int maxSubSequence3(vector<int> A, int n) {
    int tempMax = A[0]; // 以该数结尾的序列的最大和
    int resultMax = A[0];
    for (int i = 1; i < n; i++) {
        
        if (tempMax < 0) {
            tempMax = A[i];
        } else {
            tempMax += A[i];
        }
        
        resultMax = tempMax > resultMax ? tempMax : resultMax;
        
    }
    return resultMax;
}