算法题---最大子序和

本题使用动态规划的思想，创建一维数组dp(n)

1. 初始化与源数组相同，即将原数组进行拷贝

2. 状态转移方程是：如果dp[i-1] > 0 then dp[i] = dp[i-1] + nums[i] 否则 保持dp[i]值不变

3. 求取dp中的最大值，即为最大子序和

代码如下

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