专题网站开发工具有哪些,网上自己怎么注册公司,wordpress新用户权限,陕西省住房建设厅官方网站❓ 剑指 Offer 42. 连续子数组的最大和
难度#xff1a;简单
输入一个整型数组#xff0c;数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1…❓ 剑指 Offer 42. 连续子数组的最大和
难度简单
输入一个整型数组数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大为 6。 提示 1 a r r . l e n g t h 1 0 5 1 arr.length 10^5 1arr.length105$-100 arr[i] 100
注意本题与 53. 最大子数组和 相同。
思路动态规划
定义 dp 数组 dp[i]代表以元素 nums[i] 为结尾的连续子数组最大和。
若 dp[i−1] 0 说明 dp[i−1]对 dp[i] 产生负贡献即 dp[i−1]nums[i] 还不如 nums[i] 本身大。 当 dp[i−1]0 时执行 d p [ i ] d p [ i − 1 ] n u m s [ i ] dp[i]dp[i−1]nums[i] dp[i]dp[i−1]nums[i]当 dp[i−1]0 时执行 d p [ i ] n u m s [ i ] dp[i]nums[i] dp[i]nums[i] 初始状态 dp[0]nums[0]即以 nums[0] 结尾的连续子数组最大和为nums[0]。
优化
观察发现 dp[i] 只与 dp[i−1] 和 nums[i] 有关系因此可以第一个变量 sum 存储 dp[i] 的值即存储以元素 nums[i] 为结尾的连续子数组最大和。由于省去 dp 列表使用的额外空间因此空间复杂度从 O ( n ) O(n) O(n) 降至 O ( 1 ) O(1) O(1)。
代码(C、Java)
C
class Solution {
public:int maxSubArray(vectorint nums) {int ans nums[0];int sum 0;for(int num : nums){sum sum 0 ? num : sum num;ans max(ans, sum);}return ans;}
};Java
class Solution {public int maxSubArray(int[] nums) {int ans nums[0];int sum 0;for(int num : nums){sum sum 0 ? num : sum num;ans Math.max(ans, sum);}return ans;}
}运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n 为数组 nums 的长度我们只需要遍历一遍数组即可求得答案。空间复杂度 O ( 1 ) O(1) O(1)我们只需要常数空间存放若干变量。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
