leetcode53最大子序列和java题解（贪心）

1.题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
2.想法
（1）直接两个for暴力找每个序列，然后在其中找到最大值
时间复杂度n的平方
（2）贪心：每次找该位置的最优解，将当前值与子序列比较，将较大值赋值给当前值。若较大值比最大值大则赋值给最大值，这样能保证每个位置的最优解，最终找到最大值
时间复杂度n
3.图解
4.自己题解

class Solution {
    public int maxSubArray(int[] nums) {
      int max=nums[0];
      int cur=nums[0];
      for(int i=1;i<nums.length;i++)
      {
         cur=(nums[i]>cur+nums[i])?nums[i]:cur+nums[i];
         max=(max>cur)?max:cur;
      }  
      return max;
    }
}

5.分治法
留空
6.动态规划
留空