来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
给定一个整数数组 nums?，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释:?连续子数组?[4,-1,2,1] 的和最大，为?6。
思路：找到一个具有最大和的连续子数组肯定需要遍历整个数组 如果出现了负数那么肯定中途会有减小的可能 那么我们必须要用一个变量去存储这个最大值 每次遍历一个元素的时候我们都需要对这个数进行更新
遍历整个数组 当前sum值小于等于0时 那么证明前面的子数组的和对后面的数没有增加的效果 那么就对sum值进行更新 更新为当前数组中的值 否则 更新sum值为前面的子数组的和的值加上当前值 每遍历一个数
都要对整个数组中的最大连续子数组的和的值进行更新 即更新great_sum 一次遍历结束后 那么则找到最大值
public class MaxSubArrayDemo53 { public static int maxSubArray(int[] nums){ int sum = 0;//用来保存当前的连续数组和的最大值 int great_sum = Integer.MIN_VALUE;//用来保存整个数组的最大连续子数组和的值 for(int val:nums){ if(sum<=0){//求当前连续数组的最大值 如果是小于等于0 那么前面的部分对后面的部分没有增加的作用 故进行舍弃 sum=val; }else{ sum+=val; } //每遍历一个数 那么我们都需要最大值 进行更新 great_sum = Math.max(sum, great_sum); } return great_sum; } //测试 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.next().toString(); String[] str1 = str.split(","); int len = str1.length; int[] nums = new int[len]; for(int i=0; i<len; i++){ nums[i] = Integer.parseInt(str1[i]); } int res = maxSubArray(nums); System.out.println(res); } }