53. 最大子序和

题目描述 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。 https://leetcode-cn.com/problems/maximum-subarray/ 解法1 – 使用DP,O(n) 我们定义一维数组|dp| = |nums|,dp[i]表示必须使用nums[i]元素,得到的连续子数组的最大和。那么有dp[i] = max(nums[i], dp[i – 1] + nums[i])。 解释一下,如果前面累积的最大和是负数,那么使用累积的和与nums[i]相加会使得和更小,我们还不如直接使用nums[i]作为新的连续子数组。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 我们观察到dp[i]只依赖于dp[i-1],因此我们可以使空间复杂度压缩到O(1)。 解法2 – 分治法,O(nlogn) 我们定义函数maxSubArray(nums, l, r),表示区间[l, r]内找到的连续子数组的最大和。那么在区间[l, r]内的连续子数组最大和有3种来源: 来源于[l, m) (m = (l + r) / 2),记为max1; 来源与(m, r],记为max2; 来源于跨中间元素m的区间,记为max3 那么[l, r]区间的连续子数组最大和有max(max1, max2, max3)。其中,第3种情况比较复杂。我们需要从m的左右两侧出发,通过扫描来求和,如图1所示。 我们递归求解区间[l,…

Read more

321. 拼接最大数

题目描述 给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。 说明: 请尽可能地优化你算法的时间和空间复杂度。 示例 1: 输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3] 示例 2: 输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4]…

Read more