leetcode53-最大子序和

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

思路 ： 动态规划问题
1、 状态方程：dp[i]=max(dp[i-1])+nums[i]，该问题只依赖于比i小的O(1)子问题。
2、时间复杂度：O(N)。
3、空间复杂度：O(N)，可优化为O(1)。

代码 ：

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int iter_var = nums[0];
        int ans = nums[0];
        for(int i = 1; i < n; i++){
            iter_var = Math.max(iter_var+nums[i], nums[i]);
            ans = Math.max(ans, iter_var);
        }
        return ans;
    }
}