LeetCode 53. 最大子序和：

53. 最大子序和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

連結：https://leetcode-cn.com/problems/maximum-subarray 

方法1 暴力法：

思路：（略）

時間複雜度：O(n^2)

空間複雜度：O(1)

// 暴力法：
int maxSubArray(vector<int>& nums) {
    int max = INT_MIN;           // 初始值一定要定義成理論上的最小最大值
    int numsSize = nums.size();  // 不用每次計算長度，效率更高，耗時更少
    for (int i = 0; i < numsSize/*nums.size()*/; i++)
    {
        int sum = 0;
        for (int j = i; j < numsSize/*nums.size()*/; j++)
        {
            sum += nums[j];
            max = max > sum ? max : sum; 
        }
    }
    return max;
}
           

方法2 動态規劃：

思路：

dp[i]表示nums中以nums[i]結尾的最大子序和，dp[i]有兩種可能的情況，取較大者：

（1）要麼是目前數字nums[i](目前數nums[i]比每一輪循環中的前n項和更大，注意外循環起點不同)，

（2）要麼是每一輪循環中的前n項和更大（每一輪循環中的前n項和大于目前數nums[i]，注意外循環起點不同）

時間複雜度：O(n)

空間複雜度：O(1)  空間複雜度可優化至O(1)，因為隻需要知道dp的前一項，可以用int代替一維數組

// dp（記憶體優化版，一位數組代替）：
int maxSubArray(vector<int>& nums) {
    int dp = nums[0];                       // 如果輸入是[1]的話，則傳回nums[0]
    int maxVul = dp;
    for (int i = 1; i < nums.size(); i++)
    {                                       // dp[i]表示nums中以nums[i]結尾的最大子序和
        dp = max(nums[i], nums[i] + dp);    // 因為隻需要知道dp的前一項，可以用int代替一維數組
        maxVul = max(maxVul, dp); 
    }
    return maxVul;
}


// 使用dp數組（相對于上面方式，浪費記憶體空間）
int maxSubArray(vector<int>& nums) {
    int maxVul = 0;
    //dp[i]表示nums中以nums[i]結尾的最大子序和
    vector<int> dp(nums.size());                // 一定要配置設定大小才行
    dp[0] = nums[0];                            // 如果輸入是[1]的話，則傳回nums[0]
    maxVul = dp[0];
    for (int i = 1; i < nums.size(); i++)       // i從1開始才能有前一項dp[i - 1]，且dp[0]已經定義過了
    {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);      
        maxVul = max(maxVul, dp[i]);
    }

    return maxVul;
}
           

方法3 分治法和貪心法（貪心法感覺類似于dp）：

以後有時間研究~