Q1

:::info 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。 :::

动态规划

  • 对于一个数组Array任意下标i(i > 0)，定义dp[i]为到下标i的最大子数组和:

最大子数组问题 - 图1

  1. int maxSubArray(vector<int>& nums) {
  2.     int len = nums.size();
  3.     if (len == 0)
  4.     {
  5.         return 0;
  6.     }
  7.     int *dp = new int[len];
  8.     dp[0] = nums[0];
  9.     int maxSum = nums[0];
  10.     for (int i = 1; i < len; i++)
  11.     {
  12.         dp[i] = max(dp[i-1] + nums[i], nums[i]);
  13.         maxSum = max(maxSum, dp[i]);
  14.     }
  15.     return maxSum;
  16. }
  • 由于dp[i]只和dp[i-1]有关，上述写法可以优化，只需要定义一个变量用来描述dp[i-1]
    1. int maxSubArray(vector<int>& nums) {
    2.   int len = nums.size();
    3.   if (len == 0)
    4.   {
    5.       return 0;
    6.   }
    7.   int pre = 0;
    8.   int maxSum = nums[0];
    9.   for (int i = 0; i < len; i++)
    10.   {
    11.       pre = max(pre + nums[i], nums[i]);
    12.       maxSum = max(maxSum, pre);
    13.   }
    14.   return maxSum;
    15. }