最大子序和
先給題
輸入一個整型數組，數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。
要求時間複雜度為O(n)。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
有三種演算法，暴力破解、分治、還有線性，題目要求時間複雜度為O(n)，我們先拋開題目不談，我們先談一下這三種情況。
1.暴力破解（這個沒啥可說的，直接上程式碼了）
//暴力破解法
maxarray findMaximumSubarrayBruteForce(int* a, int low, int high) {
maxarray num;
num.low = low, num.high = low, num.sum = a[low];//默認第一個是最大子數組
for (int i = low; i <= high; i++) {
int sum = 0, left = i;
for (int j = i; j <= high; j++) {
sum += a[j];
if (sum > num.sum) {
num.low = left;
num.high = j;
num.sum = sum;
}
}
}
return num;
}
2.分治解法
（1）先說未優化的分治解法，分治其實就是分三種情況，
定一個mid值（選取數組中間），要麼最大子數組全部在mid的左半部分，要麼在右半部分，要麼就是在mid附近（即既包含左半部分也包含右半部分）
程式碼如下：
struct maxarray {
int low;
int high;
int sum;
};
//求跨越中點的最大子數組
maxarray findMaxCrossingSubarray(int* a, int low, int mid, int high) {
maxarray num;
int leftsum = 0, rightsum = 0, sum = 0;
for (int i = mid; i >= low; i–) {
sum += a[i];
if (sum > leftsum) {
leftsum = sum;
num.low = i;
}
}
sum = 0;
for (int i = mid + 1; i <= high; i++) {
sum += a[i];
if (sum > rightsum) {
rightsum = sum;
num.high = i;
}
}
num.sum = leftsum + rightsum;
return num;
}
//分治法
maxarray findMaximumSubarray(int* a, int low, int high) {
if (high == low) {
maxarray num;
num.low = low;
num.high = high;
num.sum = a[low];
return num;
}
else {
int mid = (high + low) / 2;
maxarray leftnum = findMaximumSubarray(a, low, mid);
maxarray rightnum = findMaximumSubarray(a, mid + 1, high);
maxarray crossingnum = findMaxCrossingSubarray(a, low, mid, high);
if (leftnum.sum >= rightnum.sum && leftnum.sum >= crossingnum.sum)
return leftnum;
else if (rightnum.sum >= leftnum.sum && rightnum.sum >= crossingnum.sum)
return rightnum;
else
return crossingnum;
}
}
以上程式碼是求最大子數組和的問題，那麼如果要求子數組長度也是最大呢，像上部分程式碼，如果 輸入 0 0 0 0 那麼得到的結果 low = 1 high = 1 sum = 0（數組從1開始）
那麼就要在上述判斷中再判斷high-low的大小 決定返回哪一個了（這裡就不進行列舉了）
（2）根據演算法導論的思考題，我們可以對這個演算法進行一些優化，當n小於某個值時，暴力破解的效率會更高一些
我們先來計算一下暴力破解和分治所需要的時間（由於時間太短，所以要用到毫秒來計算）
計算毫秒是//www.cnblogs.com/xkfz007/archive/2011/11/14/2248394.html從這裡摘取的（哎，我太菜了）
int test(int* a, int length) {
TIMEB ts1, ts2;
TIME_T t1, t2;
ftime(&ts1);
maxarray ab = findMaximumSubarrayBruteForce(a, 1, length);
ftime(&ts2);
cout << ab.low << ” ” << ab.high << ” ” << ab.sum << endl;
t1 = (TIME_T)ts1.time * 1000 + ts1.millitm;
t2 = (TIME_T)ts2.time * 1000 + ts2.millitm;
printf(“The difference is: %I64d seconds\n”, t2 – t1);
ftime(&ts1);
maxarray aa = findMaximumSubarray(a, 1, length);
ftime(&ts2);
cout << aa.low << ” ” << aa.high << ” ” << aa.sum << endl;
t1 = (TIME_T)ts1.time * 1000 + ts1.millitm;
t2 = (TIME_T)ts2.time * 1000 + ts2.millitm;
printf(“The difference is: %I64d seconds\n”, t2 – t1);
return 1;
}
這是運行結果的測試，利用rand隨機生成的數，輸入的是n值，我們發現當n到達400時，才有了時差，所以很難在這上面解決時間問題。
我從//blog.csdn.net/zxhio/article/details/82290307?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.control這篇文章中得知了在10以內 效率是暴力快，
所以改良將high==low 的判斷改為 high-low<10 利用暴力破解即可，這便是改良後的分治演算法。
3.最後到線性解法了
已知[1..j]的最大子數組，計算[1..j+1]最大子數組的思路：[1..j+1]的最大子數組要麼是[1..j]的最大子數組，要麼是某個子數組[i..j+1] (1 <= i <= j+1 )。
為了方便理解這句話，我們先來舉個例子
首先我們默認數組第一位是最大數組，也就是[1,1]是最大的子數組，那麼[1,2]的最大子數組有幾種情況呢？[1,1]也就是我們已經記錄的最大子數組maxsum。[2]或者[1,2]就這三種情況，也就是說如果[1,2]的值>[2]，那麼[2]就不是最大子數組，則去比較maxsum和[1,2],如果[1,2]的值<[2],那麼我們重置目前的sum值（sum記錄尋找過程中的最大子數組，即[j]和[1,j+1]中較大的值），讓[2]的值和maxsum去比較。
同理，當求[1,3]時，我們已經知道了[1,2]的最大子數組，那麼情況就分為三種了[1,2]的最大子數組，[3]或者[1,2,3],那麼就比較[1,2,3]和[3]，讓大的一方去和maxsum去比較。
好，理解了原理，我們就可以寫程式碼了。
maxarray findMaximumSubarrayLinear(int* a, int low, int high) {
maxarray num;
num.low = low, num.high = low, num.sum = a[low];//默認第一個是最大子數組
int sum = a[low], left = low;
for (int i = low + 1; i <= high; i++) {
if (sum + a[i] > a[i])
sum += a[i];
else
{
sum = a[i];
left = i;
}
if (sum > num.sum) {
num.low = left;
num.high = i;
num.sum = sum;
}
}
return num;
}
這是記錄位置的寫法。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = nums[0], maxsum = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (sum + nums[i] > nums[i])
sum += nums[i];
else
sum = nums[i];
if (sum > maxsum)
maxsum = sum;
}
return maxsum;
}
};
這個是關於題的。
