[数据结构与算法]Leetcode053(最大子序和)（动态规划）

题目：

描述：

?自己写的代码（解出来了，但是耗时太长）：

题解：

思路：

?代码：

题目：

https://leetcode-cn.com/problems/maximum-subarray/

描述：

?自己写的代码（解出来了，但是耗时太长）：

class Solution {
    public int maxSubArray(int[] nums) {
  //首先找到第一个>0的数，找不到就找最大的负数，并直接返回
        int l=nums.length;
        int max=nums[0];//要返回的最大值
        int i=0;
        for(i=0;i<l;i++){
            max=Math.max(max,nums[i]);
            if(nums[i]>0) break;
        }
        //假如i==l-1，说明找不到正数返回最大的负数
        if(i==l-1) return  max;
        else{
            //利用滑动窗口的思想进行解题
            int left,right; left=right=i;//初始化窗口起点和终点
            int temp=0;
            while(right<l){
                temp=0;
                if(left==right) temp=nums[left];
                else {
                    for(int k=left;k<=right;k++){
                        temp+=nums[k];
                    }
                }
                max=Math.max(temp,max);
                right++;
                //right++完判断一下有没有出界
                //这里为什么要判断一下，是因为nums={1,-1,-2}这种情况right会出界=3
                if(right==l) break;
                //起点移到终点位置
                if(temp<0&&nums[right]>=0){
                    left=right;
                }
            }
        }
        return max;
    }
}

明显我是判断条件写的太多了，题解中给出的答案我俩思路一样，他就很简洁

题解：

思路：

?代码：

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}