1. 原题链接
https://leetcode.com/problems/maximum-subarray/discuss/
2. 题目要求
给定一个整型数组，返回其子串之和的最大值
例如，[-2,1,-3,4,-1,2,1,-5,4]中，[4,-1,2,1]可以构成最大子串之和6
3. 解题思路
对数组进行一次遍历，每次加入一个元素前，先判断其加入后累加和与该元素的大小，取最大者。然后每遍历一个元素，选取当前的最大子串之和。
4. 代码实现
public class MaximumSubarray53 {
public static void main(String[] args) {
int[] nums ={-2,1,-3,4,-1,2,1,-5,4};
System.out.println(maxSubArray(nums));
}
public static int maxSubArray(int[] nums){
int sumTemp =nums[0], maxRes = nums[0];
for(int i =1;i<nums.length;i++){
sumTemp = Math.max(sumTemp+nums[i],nums[i]);
maxRes = Math.max(sumTemp,maxRes);
}
return maxRes;
}
}