前言
💫你好，我是辰chen，一个正在考研途中的 s o p h o m o r e sophomore sophomore d o g dog dog😖
💫目前每日一题主要来自于 leetcode，当然也可能来自洛谷或其他刷题平台，每日一题专栏地址：每日一题
💫欢迎大家的关注，我的博客主要关注于考研408以及AIoT的内容
🌟 每日一题我会给出两种代码， C C C版以及 P y t h o n Python Python版，刷题的目的是为了考研的算法题以及机试(或手写代码)
🌟这也是为什么不用 C + + C++ C++ 而用 C C C， P y t h o n Python Python版代码是为了提高语言熟练度(以后开发大概率用的是 P y t h o n Python Python
🌟 坚持打卡！踏踏实实走好每一步
以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)，欢迎大家的关注：
💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解
👊每日一句：天行健，君子以自强不息。
大家做完可以在评论区打卡留言??，形成良好的学习氛围，一起进步！
LeetCode 53. 最大子数组和
题目描述：
给你一个整数数组 n u m s nums nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1
<
=
n
u
m
s
.
l
e
n
g
t
h
<
=
1
0
5
1 <= nums.length <= 10^5
1<=nums.length<=105
?
1
0
4
<
=
n
u
m
s
[
i
]
<
=
1
0
4
-10^4 <= nums[i] <= 10^4
?104<=nums[i]<=104
C版AC代码：
int maxSubArray(int* nums, int numsSize){
int b = nums[0], a = 0;
int res = nums[0];
for (int i = 1; i < numsSize; i ++ ){
a = fmax(b + nums[i], nums[i]);
res = fmax(res, a);
b = a;
}
return res;
}
Python版AC代码：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
a, b, n, res = 0, nums[0], len(nums), nums[0]
for i in range(1, n):
a = max(b + nums[i], nums[i])
res = max(res, a)
b = a
return res
LeetCode 918. 环形子数组的最大和
题目描述：
给定一个长度为 n n n 的环形整数数组 n u m s nums nums ，返回 n u m s nums nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， n u m s [ i ] nums[i] nums[i] 的下一个元素是 n u m s [ ( i + 1 ) nums[(i + 1) % n] nums[(i+1) ， n u m s [ i ] nums[i] nums[i] 的前一个元素是 n u m s [ ( i ? 1 + n ) nums[(i - 1 + n) % n] nums[(i?1+n) 。
子数组 最多只能包含固定缓冲区 n u m s nums nums 中的每个元素一次。形式上，对于子数组 n u m s [ i ] , n u m s [ i + 1 ] , . . . , n u m s [ j ] nums[i], nums[i + 1], ..., nums[j] nums[i],nums[i+1],...,nums[j] ，不存在 i < = k 1 , k 2 < = j i <= k_1, k_2 <= j i<=k1?,k2?<=j 其中 k 1 % n = = k 2 % n k_1 \% n == k_2 \% n k1?%n==k2?%n 。
示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示：
n
=
=
n
u
m
s
.
l
e
n
g
t
h
n == nums.length
n==nums.length
1
<
=
n
<
=
3
?
1
0
4
1 <= n <= 3 * 10^4
1<=n<=3?104
?
3
?
1
0
4
<
=
n
u
m
s
[
i
]
<
=
3
?
1
0
4
?
?
?
?
?
?
?
-3 * 10^4 <= nums[i] <= 3 * 10^4???????
?3?104<=nums[i]<=3?104???????
思路： 有两种可能，第一种即为答案在数组中间，那么就转成了本博客的第一题；第二种即为答案在数组两边，那么我们就用数组的总和减最小子序和，其中会出现特殊情况即最小子序和 == 数组的和，这种情况下数组全为负数或全为0，那么此时我们输出数组中的最大值即可。
C版AC代码：
int maxSubarraySumCircular(int* nums, int numsSize){
int pastf = nums[0], pastg = nums[0];
int nowf = 0x3f3f3f3f, nowg = -0x3f3f3f3f;
int res = nums[0], sum = nums[0], sumin = nums[0], sumax = nums[0];
for (int i = 1; i < numsSize; i ++ ){
sum += nums[i];
nowf = fmax(pastf + nums[i], nums[i]);
nowg = fmin(pastg + nums[i], nums[i]);
res = fmax(res, nowf);
sumin = fmin(sumin, nowg); // 子数组的最小值
sumax = fmax(sumax, nums[i]); // 数组中的最大值
pastf = nowf, pastg = nowg;
}
// 如果有 sum - sumin == 0, 证明数组全为负,那么就输出整个数组中的最大值
res = fmax(res, sum - sumin == 0 ? sumax : sum - sumin);
return res;
}
Python版AC代码：
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
nowf, pastf, nowg, pastg = -0x3f3f3f3f, nums[0], 0x3f3f3f3f, nums[0]
n, res, numin, numax, suml = len(nums), nums[0], nums[0], nums[0], nums[0]
for i in range(1, n):
# 动态规划
nowf = max(pastf + nums[i], nums[i])
nowg = min(pastg + nums[i], nums[i])
# 更新最大值，最小值，总和
res = max(res, nowf)
numax = max(numax, nums[i])
numin = min(numin, nowg)
suml += nums[i]
pastf, pastg = nowf, nowg
if suml - numin == 0:
res = max(res, numax)
else:
res = max(res, suml - numin)
return res
