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记录，一个记录二维数组中每一列中最大的数，一个记录最终结果。