题目描述

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

示例

代码

class Soluttion { public int maxSubArray(int[] nums) { int ans = nums[0]; //该变量是保存最终输出结果的变量 int sum = 0; //每次循环遍历的时候元素的求和变量 //循环遍历需要进行处理的数组 for (int num : nums) { //如果此时的sum大于0，则sum对结果有增益效果，则sum保存并加上当前的遍历数字 if (sum > 0) { sum += num; } else { //如果sum小于等于0，则说明sum对结果无增益效果，需要舍弃，则将当前的数值num赋值给sum sum = num; } //将新的sum与ans之前存储的结果进行比较，并且将较大的重新赋值给ans ans = Math.max( ans, sum); } //最后返回结果是最大的和 return ans; // System.out.println("输出最大值的和"+" "+ ans); } public static void main(String[] args) { int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; Soluttion gfh = new Soluttion(); gfh.maxSubArray(nums); } }

代码说明：

这里使用的是动态规划的方法,要求的是一个连续的子序列的最大的和。首先我们执行的操作是对这个nums数组进行操作，代码中使用了两个变量，第一个变量sum，当sum大于0时，此时是有增益效果的，所以遍历的时候我们就是在sum的基础上加上num,如果sum小于零,则当前寻找的这个子序列，已经没有意义了， 重新将num的值赋值给sum，继续寻找新的最大和子序列。同时每一轮都要进行判断是否当前轮的sum大于之前赋值的ans,如果大于ans，就将此时的sum赋值给ans存储起来，如果小于ans就保持原来的ans的值保持不变，这里存在大于小于的原因是因为当前遍历的数可能是正的或负的，所以上面这种情况的判断。将所有的数组元素遍历结束后，就能找到最大的和的连续子序列。