本文章是⭐️小Y学算法⭐️ 的内容,该专栏还有多篇优质内容在等待你观看,现在点击右上角 点击这个————🚀订阅专栏🚀 就可以免费观看 多篇相关内容的文章啦!
📢前言
🌲 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程😜 🌲 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题 🌲 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧🧐! 🌲 今天是力扣算法题持续打卡第17天🎈!
🌲原题样例
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1 :
输入:nums = [ - 2 , 1 , - 3 , 4 , - 1 , 2 , 1 , - 5 , 4 ]
输出:6
解释:连续子数组 [ 4 , - 1 , 2 , 1 ] 的和最大,为 6 。
示例 2 :
输入:nums = [ 1 ]
输出:1
示例 3 :
输入:nums = [ 0 ]
输出:0
示例 4 :
输入:nums = [ - 1 ]
输出:- 1
示例 5 :
输入:nums = [ - 100000 ]
输出:- 100000
提示:
1 <= nums.length <= 3 * 104 -105 <= nums[i] <= 105
🌻C#方法一:动态规划
思路解析 动态规划 核心思想:子问题重复调用
sum表示当前连续子数组的和,max表示当前和最大的连续子数组; 若nums[i] > sum + nums[i],即nums[i]比前面的所有项加起来都大,则可以舍弃前面的项,sum = nums[i];否则sum加上nums[i]; 每次得出的sum都与max比较,得出当前最大的和。
代码:
public class Solution {
public int MaxSubArray ( int [ ] nums) {
int sum = nums[ 0 ] ;
int max = nums[ 0 ] ;
for ( int i = 1 ; i < nums. Length; i++ )
{
if ( nums[ i] > sum + nums[ i] ) sum = nums[ i] ;
else sum = sum + nums[ i] ;
if ( sum > max) max = sum;
}
return max;
}
}
执行结果
通过
执行用时:88 ms,在所有 C# 提交中击败了87.62 % 的用户
内存消耗:25.5 MB,在所有 C# 提交中击败了25.74 % 的用户
复杂度分析
时间复杂度:O ( n)
空间复杂度:O ( 1 )
🌻C#方法二:分治法
思路解析 这个分治法,我也没有看得很明白,这里把力扣解答放了上来给大家参考一下!
代码:
public class Solution {
public class Status {
public int lSum, rSum, mSum, iSum;
public Status ( int lSum_, int rSum_, int mSum_, int iSum_) {
lSum = lSum_; rSum = rSum_; mSum = mSum_; iSum = iSum_;
}
}
public Status pushUp ( Status l, Status r) {
int iSum = l. iSum + r. iSum;
int lSum = Math. Max ( l. lSum, l. iSum + r. lSum) ;
int rSum = Math. Max ( r. rSum, r. iSum + l. rSum) ;
int mSum = Math. Max ( Math. Max ( l. mSum, r. mSum) , l. rSum + r. lSum) ;
return new Status ( lSum, rSum, mSum, iSum) ;
}
public Status getInfo ( int [ ] a, int l, int r) {
if ( l == r) {
return new Status ( a[ l] , a[ l] , a[ l] , a[ l] ) ;
}
int m = ( l + r) >> 1 ;
Status lSub = getInfo ( a, l, m) ;
Status rSub = getInfo ( a, m + 1 , r) ;
return pushUp ( lSub, rSub) ;
}
public int MaxSubArray ( int [ ] nums) {
return getInfo ( nums, 0 , nums. Length - 1 ) . mSum;
}
}
执行结果
通过
执行用时:76 ms,在所有 C# 提交中击败了99.63 % 的用户
内存消耗:26.9 MB,在所有 C# 提交中击败了5.03 % 的用户
复杂度分析
时间复杂度:O ( n)
空间复杂度:O ( long n)
🌻Java 方法一:动态规划
思路解析
代码:
class Solution {
public int maxSubArray ( int [ ] nums) {
int pre = 0 , maxAns = nums[ 0 ] ;
for ( int x : nums) {
pre = Math . max ( pre + x, x) ;
maxAns = Math . max ( maxAns, pre) ;
}
return maxAns;
}
}
执行结果
通过
执行用时:1 ms,在所有 Java 提交中击败了92.33 % 的用户
内存消耗:38.2 MB,在所有 Java 提交中击败了79.37 % 的用户
复杂度分析
时间复杂度:O ( n)
空间复杂度:O ( 1 )
🌻Java方法二:分治法
思路解析 和上面的C#第二种解法一个思路,代码有所区别
代码:
class Solution {
public class Status {
public int lSum, rSum, mSum, iSum;
public Status ( int lSum, int rSum, int mSum, int iSum) {
this . lSum = lSum;
this . rSum = rSum;
this . mSum = mSum;
this . iSum = iSum;
}
}
public int maxSubArray ( int [ ] nums) {
return getInfo ( nums, 0 , nums. length - 1 ) . mSum;
}
public Status getInfo ( int [ ] a, int l, int r) {
if ( l == r) {
return new Status ( a[ l] , a[ l] , a[ l] , a[ l] ) ;
}
int m = ( l + r) >> 1 ;
Status lSub = getInfo ( a, l, m) ;
Status rSub = getInfo ( a, m + 1 , r) ;
return pushUp ( lSub, rSub) ;
}
public Status pushUp ( Status l, Status r) {
int iSum = l. iSum + r. iSum;
int lSum = Math. max ( l. lSum, l. iSum + r. lSum) ;
int rSum = Math. max ( r. rSum, r. iSum + l. rSum) ;
int mSum = Math. max ( Math. max ( l. mSum, r. mSum) , l. rSum + r. lSum) ;
return new Status ( lSum, rSum, mSum, iSum) ;
}
}
执行结果
通过
执行用时:76 ms,在所有 C# 提交中击败了99.63 % 的用户
内存消耗:26.9 MB,在所有 C# 提交中击败了5.03 % 的用户
复杂度分析
时间复杂度:O ( n)
空间复杂度:O ( long n)
💬总结
今天是力扣算法题打卡的第十七天! 文章采用 C#
和 Java
两种编程语言进行解题 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们 那今天的算法题分享到此结束啦,明天再见!