By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、最大子序和

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

1.1、解题思路

首先我们取出第一个数字，作为临时的最大值 ，然后看下面的算法吧，比较简单

1.2、算法

public int maxSubArray(int[] nums) {
    int maxTemp = nums[0];
    int max = nums[0];
    for(int i = 1; i < nums.length; ++i) {
        //当前元素, 当前元素位置的最大和
        maxTemp = Math.max(nums[i], maxTemp + nums[i]);

        max = Math.max(max, maxTemp);
    }
    return max;
}

1.3、测试

@Test
public void test(){

    int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
}

控制台：

6

​

ContactAuthor