leetcode日记（41）最大子数组和

以前大一的时候做过这题jpg，应该是个很经典的动态规划。

我首先的想法创建二维数组，横列代表起始位置纵列代表结束位置，依次补全数组，后来发现时间复杂度太高了：

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();int t=0;int maxx=-2147483648;for(int i=0;i<n;i++){for(int j=i;j<n;j++){if(i==j) t=nums[i];else t+=nums[j];maxx=max(t,maxx);}}return maxx;}
};

发现答案只用一个循环，细想了一下终于明白了答案的思路，比上面要简洁得多

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();int t=0;int maxx=nums[0];for(int i=0;i<n;i++){t=max(nums[i],t+nums[i]);maxx=max(maxx,t);}return maxx;}
};

答案的做法是只用两个int记录，一个记录二维数组中每一列中最大的数，一个记录最终结果。