golang刷leetcode 技巧（31）连续数列

给定一个整数数组（有正数有负数），找出总和最大的连续数列，并返回总和。

示例：

输入：[-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

解题方案一 (动态规划)

思路

假设数组名称为arr，结果数组为result

result[0] = arr[0]result[0] + arr[1]=1result[1] + arr[2] = 1 + -3 = -2arr[2] = -3

1. 总结可得如下规律

1. 最终只需取得result[]中值最大的数即为结果

代码

   public static int maxSubArray(int[] arrs) {
        int len = arrs.length;
        int maxNum = arrs[0];
        int[] result = new int[arrs.length];
        result[0] = maxNum;
        for (int i = 1; i < len; i++) {
            int a = result[i - 1] + arrs[i];  //保留前边的序列
            int b = arrs[i];  //不保留前边的序列

            int curMax = Math.max(a, b);
            result[i] = curMax;

            if (curMax > maxNum) {
                maxNum = curMax;
            }
        }
        return maxNum;
    }

代码优化

由于上述过程中,创建了result数组,但是实际上每次循环时,当前数字计算完之后就没有其他用处了，所以此处可以使用arrs数组作为result数组来用，优化后如下

    public static int maxSubArray(int[] arrs) {
        int len = arrs.length;
        int maxNum = arrs[0];
        for (int i = 1; i < len; i++) {
            int a = arrs[i - 1] + arrs[i];  //保留前边的序列
            int b = arrs[i];  //不保留前边的序列

            int curMax = Math.max(a, b);
            arrs[i] = curMax;

            if (curMax > maxNum) {
                maxNum = curMax;
            }
        }
        return maxNum;
    }

代码实现

func maxSubArray(nums []int) int {
sum:=0
max:=0
for i,n:=range nums{
    if i==0{
        max=n
        sum=n
        continue
    }
    if sum+n>n{
        sum+=n
    }else{
        sum=n
    }
    if max<sum{
        max=sum
    }
}
return max
}