前言

💫你好，我是辰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 。

  

 

  
1
  
2
  
3
 

示例 2：

输入：nums = [1]
输出：1

  

 

  
1
  
2
 

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

  

 

  
1
  
2
 

提示：

$1<=nums.length<=10^5$
$-10^4<=nums[i]<=10^4$

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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

LeetCode 918. 环形子数组的最大和

题目描述：

给定一个长度为 $n$ 的环形整数数组 $nums$ ，返回 $nums$ 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， $nums[i]$ 的下一个元素是 $nums[(i+1)$ ， $nums[i]$ 的前一个元素是 $nums[(i-1+n)$ 。

子数组 最多只能包含固定缓冲区 $nums$ 中的每个元素一次。形式上，对于子数组 $nums[i],nums[i+1],...,nums[j]$ ，不存在 $i<=k_1,k_2<=j$ 其中 $k_1\%n==k_2\%n$ 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

  

 

  
1
  
2
  
3
 

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

  

 

  
1
  
2
  
3
 

示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

  

 

  
1
  
2
  
3
 

提示：

$n==nums.length$
$1<=n<=3\ast 10^4$
$-3\ast 10^4<=nums[i]<=3\ast 10^4$

思路： 有两种可能，第一种即为答案在数组中间，那么就转成了本博客的第一题；第二种即为答案在数组两边，那么我们就用数组的总和减最小子序和，其中会出现特殊情况即最小子序和 == 数组的和，这种情况下数组全为负数或全为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;
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

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

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/124230850