初刷leetCode--数组系列--Maximum Subarray(连续最大子序列)
前言
今天正式进入到leetCode的刷题中,先根据数据结构划分,从与数组且Easy的问题开始。对于选题,我们没必要每一题都做,可以先阅读题目,觉得思路清晰简单的就可以直接跳过,例如开始的 Two Sum,
Remove Duplicates from Sorted Array,Remove Element,
Search Insert Position思路和实现上都没有什么难度,可以直接跳过,加快刷题速度。后边的第53题 Maximum Subarray比较有意思。今天就先从这道题入手,分析一下解题方法。
问题描述
(注:问题图片来自于leetcode截图)
这道题要求我们找到一组数组中最大的且连续的序列集合,且对解题的时间复杂度做了要求。
解题思路
初看题目,最简单的解法就是对数组做遍历,即计算出所有的 单个数,两个连续数,三个连续数…然后求最大,这样子时间复杂度就是n的阶乘,不能满足题目要求。
再想想,这个问题其实和计算的上一个状态相关,我们可以找到当前状态sum[i]与上一个状态sum[i-1]的关系,发现其实可以通过动态规划的方法来解。
- 定义状态:sum[i] 表示把当前第i个状态最后元素为num[i]的连续数组元素的和;
- 初始状态:sum[i] = num[0];
- 状态转移方程:sum[i] = max{num[i],sum[i-1] + num[i]}
根据状态定义与转移方程,我们可以开始写我们的代码:
int maxSubArray(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int[] sum = new int[len];
sum[0] = nums[0];
int max = sum[0];
for (int i = 1; i < len; i++) {
sum[i] = Math.max(nums[i], sum[i - 1] + nums[i]);
if (max <= sum[i])
max = sum[i]
}
return max;
}
今天就写到这,有问题欢迎指教!