dart实现leetcode_53

[toc]

题目：https://leetcode-cn.com/problems/maximum-subarray/

1.暴力法

  ///
  /// Author: liyanjun
  /// description: 暴力法
  ///
  int maxSubArray(List<int> nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }

    int maxNumber = nums.first;
    for (var begin = 0; begin < nums.length; begin++) {
      for (var end = begin + 1; end < nums.length; end++) {
        int sum = 0;
        for (var i = begin; i <= end; i++) {
          sum += nums[i];
        }
        maxNumber = max(sum, maxNumber);
      }
    }
    return maxNumber;
  }

空间复杂度：O(1)，时间复杂度：

1.1 暴力法优化

重复利用前面计算过的结果

// ◼ 重复利用前面计算过的结果
   int maxSubArray1(List<int> nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    int maxNumber = nums.first;
    for (var begin = 0; begin < nums.length; begin++) {
      int sum = 0;
      for (var end = begin; end < nums.length; end++) {
        sum +=nums[end];
        maxNumber = max(sum, maxNumber);
      }
    }
    return maxNumber;
  }
}

空间复杂度：O(1)，时间复杂度：

2.分治法

将序列均匀地分割成 2 个子序列

• [begin , end) = [begin , mid) + [mid , end)，mid = (begin + end) >> 1

假设 [begin , end) 的最大连续子序列和是 S[i , j) ，那么它有 3 种可能

• [i , j) 存在于 [begin , mid) 中，同时 S[i , j) 也是 [begin , mid) 的最大连续子序列和
• [i , j) 存在于 [mid , end) 中，同时 S[i , j) 也是 [mid , end) 的最大连续子序列和
• [i , j) 一部分存在于 [begin , mid) 中，另一部分存在于 [mid , end) 中
  • [i , j) = [i , mid) + [mid , j)
  • S[i , mid) = max { S[k , mid) }，begin ≤ k ＜ mid
  • S[mid , j) = max { S[mid , k) }，mid ＜ k ≤ end

代码

///
  /// Author: liyanjun
  /// description: [begin]到[end]连续子序列的和 左闭右开
  ///
  int divideConquer(List<int> nums, int begin, int end) {
    if (end - begin < 2) return nums[begin];
    int mid = (end + begin) >> 1;
    int leftMax = nums[mid - 1];
    //计算从mid-1开始往左遍历 最大值
    int leftSum = leftMax;
    for (int i = mid - 2; i >= begin; i--) {
      leftSum += nums[i];
      leftMax = max(leftMax, leftSum);
    }
    //计算从mid开始开始往右遍历 最大值
    int rightMax = nums[mid];
    int rightSum = rightMax;
    for (int i = mid + 1; i < end; i++) {
      rightSum += nums[i];
      rightMax = max(rightMax, rightSum);
    }
    return max(
        leftMax + rightMax, //横跨左右两边的最大子序列和
        max(
            divideConquer(nums, begin, mid), //左边最大子序列和
            divideConquer(nums, mid, end))); //右边最大子序列和
  }
}

空间复杂度：O(logn)，
时间复杂度$T(n)=2T(n/2)+O(n) = O(n*logn)

3.动态规划

状态定义：
假设 dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）

• 以 nums[0] –2 结尾的最大连续子序列是 –2，所以 dp(0) = –2
• 以 nums[1] 1 结尾的最大连续子序列是 1，所以 dp(1) = 1
• 以 nums[2] –3 结尾的最大连续子序列是 1、–3，所以 dp(2) = dp(1) + (–3) = –2
• 以 nums[3] 4 结尾的最大连续子序列是 4，所以 dp(3) = 4
• 以 nums[4] –1 结尾的最大连续子序列是 4、–1，所以 dp(4) = dp(3) + (–1) = 3
• 以 nums[5] 2 结尾的最大连续子序列是 4、–1、2，所以 dp(5) = dp(4) + 2 = 5
• 以 nums[6] 1 结尾的最大连续子序列是 4、–1、2、1，所以 dp(6) = dp(5) + 1 = 6
• 以 nums[7] –5 结尾的最大连续子序列是 4、–1、2、1、–5，所以 dp(7) = dp(6) + (–5) = 1
• 以 nums[8] 4 结尾的最大连续子序列是 4、–1、2、1、–5、4，所以 dp(8) = dp(7) + 4 = 5

状态转移方程：

• 如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
• 如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]

初始状态

• dp(0) 的值是 nums[0]

最终的解

• 最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)

代码

int maxSubArray3(List<int> nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    List<int> dp = List(nums.length);
    dp[0] = nums[0];
    int maxDp = dp[0];
    for (var i = 1; i < nums.length; i++) {
      if (dp[i - 1] <= 0) {
        dp[i] = nums[i];
      } else {
        dp[i] = dp[i - 1] + nums[i];
      }
      maxDp = max(maxDp, dp[i]);
    }
    return maxDp;
  }

3.1 动态规划优化

优化空间，不需要数组

///
/// Author: liyanjun
/// description: 动态规划优化
/// 优化空间
///
int maxSubArray4(List<int> nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    int dp = nums[0];
    int maxDp =dp;
    for (var i = 1; i < nums.length; i++) {
      if (dp <= 0) {
        dp = nums[i];
      } else {
       dp = dp + nums[i];
      }
      maxDp = max(maxDp, dp);
    }
    return maxDp;
  }