leetcode做题笔记整理

题目都是来自leetcode，答主使用c++语言完成，其实包括楼主自己的感想，以及会参考多种版本，分析其中的不同

最主要的目的还是楼主自己温故知识，如果能对读者有所作用的话那更是很开心的事情。

博主是语言的初学者已经算法的初学者，希望能互相学习

53. 最大子序和

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

    int maxSubArray(vector<int>& nums) {
         vector<int>dp(nums.size());
         dp[0]=nums[0];
         int max_num=dp[0];
         for(int i=1;i<nums.size();i++){
             if(dp[i-1]<0)
                 dp[i]=nums[i];
             else
                 dp[i]=nums[i]+dp[i-1];
             max_num=max(max_num,dp[i]);
         }
         return max_num;
    }
};

这道题算是博主第一次使用dp算法和领会到dp思想的一道题，其中的状态转移方程为

dp[i]=nums[i]+dp[i-1]<0?0:dp[i-1]

值得注意的是要清楚这里的状态值得是对于每一个位置所能得到的最大的序列和，所以这里的结果应该是所有的dp[i】(i=0,1...n-1)的最大值就是为本题的最终结果