第一章：动态规划设计：最大子数组

labuladong动态规划设计：最大子数组

53. 最大子序和

---

课堂上，学生排排坐。

老师：“这门课的作业，你们可以选择自己完成，也可以根据座位顺序，和你前面的同学组队（前面的同学可能和前前面的同学组了队，也可能就他一个人）。”

每个人都想把自己的作业完成得最好。

在座位i处的大佬心想：“前面可能是大大佬（可以组队, dp[i-1]+nums[i]），也可能是小小菜（组队会拖我后腿，还不如我自己nums[i]）。” 不管哪种选择，最后，他的最好成绩取这两种选择的最大值即可。

---

• dp数组含义： 以nums[i]结尾的当前最大子序和保存在dp[i] 中
• 状态转移方程：nums[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组
  • 对nums[i]而言（dp数组的含义决定了子序和是以nums[i]结尾的），若连接前面的子序列，则dp[i]=dp[i-1]+nums[i]。 若不连接，则自立门户 dp[i]=nums[i] 。根据这两种选择，直接取最大值即可 dp[i]=max(nums[i],dp[i-1]+nums[i])。

class Solution(object):
    def maxSubArray(self, nums):
        if not nums: return 0
        dp=[0 for _ in range(len(nums))]
        dp[0]=nums[0]

        for i in range(1,len(nums)):
            dp[i]=max(nums[i],dp[i-1]+nums[i])
        return max(dp)

# 也可以分开写  (但没必要，可以放到max()函数中，让函数自己判断)
# class Solution(object):
#     def maxSubArray(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         dp=[0 for _ in range(len(nums))]
#         dp[0]=nums[0]
#         for i in range(1, len(nums)):
#            # 前面是大大佬
#             if dp[i-1]>0: 
#                 dp[i]=dp[i-1]+nums[i]
#           # 前面是小小菜
#             else:
#                 dp[i]=nums[i]
#         return max(dp)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size()==0){
            return 0;
        }
        vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            dp[i]= max(dp[i-1]+nums[i],nums[i]);
        }
        return *max_element(dp.begin(),dp.end());

    }
};