前言
💫你好，我是辰chen，一个正在考研途中的sophomore dog😖
💫目前每日一题主要来自于 leetcode，当然也可能来自洛谷或其他刷题平台，每日一题专栏地址：每日一题
💫欢迎大家的关注，我的博客主要关注于考研408以及AIoT的内容
🌟 每日一题我会给出两种代码，C 版以及 Python版，刷题的目的是为了考研的算法题以及机试(或手写代码)
🌟这也是为什么不用C++ 而用 C ，Python版代码是为了提高语言熟练度(以后开发大概率用的是 Python
🌟 坚持打卡！踏踏实实走好每一步
以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)，欢迎大家的关注：
💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解
👊每日一句：天行健，君子以自强不息。
大家做完可以在评论区打卡留言✒️，形成良好的学习氛围，一起进步！
LeetCode 53. 最大子数组和
题目描述：
给你一个整数数组 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
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. 环形子数组的最大和
题目描述：
示例 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
思路： 有两种可能，第一种即为答案在数组中间，那么就转成了本博客的第一题；第二种即为答案在数组两边，那么我们就用数组的总和减最小子序和，其中会出现特殊情况即最小子序和 == 数组的和，这种情况下数组全为负数或全为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
