亲宝软件园·资讯

展开

LeetCode【面试题 16.17. 连续数列】

itaot 人气:1

题目描述

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

示例:

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

解题方案一 (动态规划)

思路

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

  1. 当只有一个数字的时候,最大的连续数列只能是这个数字,所以序号为0的位置,最大值为-2,则有result[0] = arr[0]
  2. 当有两个数字时,有两种情况
    1. 保留前边的序列,此时值为result[0] + arr[1]=
    2. 不保留前边的序列,此时值为1,即arr[1]
    3. 此时选取最大值的话为1
  3. 到第三个数字时
    1. 保留前边的序列,值为result[1] + arr[2] = 1 + -3 = -2
    2. 不保留前边的序列,值为arr[2] = -3
    3. 此时选取最大值的话为-3
  4. 以此类推的话可以得到下表
序号 0 1 2 3 4 5 6 7 8
数值(arr数组) -2 1 -3 4 -1 2 1 -5 4
保留前边的序列 -1 -4 -1 3 5 6 1 5
不保留前边的序列 1 -3 4 4 2 1 -5 4
最大值(result数组) -2 1 -3 4 4 5 6 1 4
  1. 总结可得如下规律
  2. 最终只需取得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;
    }

加载全部内容

相关教程
猜你喜欢
用户评论