Leetcode-Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

這題我沒做出來，因為暴力枚舉感覺真的太low了，網上查了一下主要有兩種方法。

Kadane演算法：

def max_subarray(A):n max_ending_here = max_so_far = A[0]n for x in A[1:]:n max_ending_here = max(x, max_ending_here + x)n max_so_far = max(max_so_far, max_ending_here)n return max_so_farn

這種演算法看起來很短，但說實話理解起來還是有一定難度的，max_ending_here代表在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和），因為最大和子串中不可能包含求和值為負的前綴，例如 【-2， 1，4】 必然不能是最大子數列， 因為去掉值為負的前綴後【-2，1】， 可以得到一個更大的子數列 【4】，所以在求max_ending_here的時候其實一直在去掉負的前綴，而max_so_far代表的就是目前為止最大子串和。這種演算法時間複雜度可以達到最優的O(N)級別。

Divide and Conquer演算法：

#include <bits/stdc++.h>nusing namespace std;nn// Function to find Maximum subarray sum using n// divide and conquernint MaximumSum(int A[], int low, int high)n{nt// If array contains only one elementntif (high == low)nttreturn A[low];nnt// Find middle element of the arrayntint mid = (low + high) / 2;nnt// Find maximum subarray sum for the left subarray nt// including the middle elementntint leftMax = INT_MIN;ntint sum = 0;ntfor (int i = mid; i >= low; i--) nt{nttsum += A[i];nttif (sum > leftMax)ntttleftMax = sum;nt}nt/*nt為什麼不是:這種寫法結果是錯的 ntfor (int i = low; i <= mid; i++)nt{nttsum += A[i];nttif (sum > leftMax)ntttleftMax = sum;nt}nt*/nnt// Find maximum subarray sum for the right subarray nt// excluding the middle elementntint rightMax = INT_MIN;ntsum = 0;t// reset sum to 0ntfor (int i = mid + 1; i <= high; i++) nt{nttsum += A[i];nttif (sum > rightMax)ntttrightMax = sum;nt}nnt// Recursively find the maximum subarray sum for left subarray nt// and right subarray and tale maximumntint maxLeftRight = max(MaximumSum(A, low, mid), ntttMaximumSum(A, mid + 1, high));nnt// return maximum of the threentreturn max(maxLeftRight, leftMax + rightMax);n}nnint main()n{ntint arr[] = { -2,1,-3,4,-1,2,1,-5,4 };ntint n = sizeof(arr) / sizeof(arr[0]);nntcout << "The Maximum sum of the subarray is " << ntttMaximumSum(arr, 0, n - 1);nntreturn 0;n}n

用分治法也可以做出來，時間複雜度O(NlogN)，其中INT_MIN is a macro that expands to the smallest (most negative) value that can be stored in a variable of type int.

INT_MAX is a macro that expands to the largest (most positive) value that can be stored in an int.這是c++的語法。英文解釋很清楚了。

但我有個疑惑在於：

/*

tfor (int i = low; i <= mid; i++)

t}

在求leftmax的時候用這種方式for循環，為什麼得出的結果就是錯誤的呢？

參考鏈接：

清晰解題： 尋找最大子數列-Kadane演算法

https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98

https://www.quora.com/What-is-INT_MIN-and-INT_MAX-in-C++

http://www.techiedelight.com/maximum-sum-subarray-using-divide-conquer/