最大子序和题目——动态规划/贪心算法办理

目录

一：题目描述
二：办理思路1——动态规划思想
三：C 语言代码实现
 四：复杂度分析
 五：办理思路2——贪心算法思想
六：具体步骤
七: C语言代码实现
八：复杂度分析

---

一：题目描述

最大子序和题目指的是在一个整数数组里，找出一个具有最大和的连续子数组（子数组最少包含一个元素），然后返回其最大和。
例如，对于数组 [-2,1,-3,4,-1,2,1,-5,4]，其连续子数组 [4,-1,2,1] 的和最大，为 6。
二：办理思路1——动态规划思想

• 界说一个数组 dp，此中 dp 代表以第 i 个元素结尾的连续子数组的最大和。
  
• 状态转移方程：dp = max(dp[i - 1] + nums, nums)。也就是说，以第 i 个元素结尾的连续子数组的最大和，要么是把第 i 个元素加入到以第 i - 1 个元素结尾的连续子数组中，要么是第 i 个元素单独作为一个子数组。
  
• 最终的最大子序和就是 dp 数组中的最大值。
  

三：C 语言代码实现

1. #include <stdio.h>
3. // 函数用于找出最大子序和
4. int maxSubArray(int* nums, int numsSize) {
5.     if (numsSize == 0) return 0;
6.     int dp[numsSize];
7.     dp[0] = nums[0];
8.     int max_sum = dp[0];
10.     for (int i = 1; i < numsSize; i++) {
11.         // 状态转移方程
12.         if (dp[i - 1] + nums[i] > nums[i]) {
13.             dp[i] = dp[i - 1] + nums[i];
14.         } else {
15.             dp[i] = nums[i];
16.         }
17.         // 更新最大和
18.         if (dp[i] > max_sum) {
19.             max_sum = dp[i];
20.         }
21.     }
23.     return max_sum;
24. }
26. int main() {
27.     int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
28.     int numsSize = sizeof(nums) / sizeof(nums[0]);
29.     int result = maxSubArray(nums, numsSize);
30.     printf("最大子序和为: %d\n", result);
31.     return 0;
32. }

复制代码

 四：复杂度分析

• 算法的时间复杂度为 (O(n))，此中 n 是数组的长度。
  

 五：办理思路2——贪心算法思想

贪心算法的核心思想在于每一步都做出当下看起来最优的选择，盼望通过局部最优解来达成全局最优解。
在最大子序和题目中，我们可以在遍历数组的过程里，连续更新当前的连续子数组和，而且在每一步都判定是否要更新最大和。
六：具体步骤

• 初始化变量：
  
  
  
  • 界说两个变量，current_sum 用于记载当前连续子数组的和，初始值设为数组的第一个元素。
    
  • max_sum 用于记载到现在为止所找到的最大子序和，初始值也设为数组的第一个元素。
    
  
  
• 遍历数组：
  
  
  
  • 从数组的第二个元素开始遍历。
    
  • 对于每一个元素 nums，有两种情况：
    
    
    
    • 如果 current_sum 加上当前元素 nums 后比 nums 自己大，那么就把 nums 加入到当前连续子数组中，即 current_sum = current_sum + nums。
      
    • 反之，说明之前的连续子数组和是负数，继续保留它会让和变小，所以舍弃之前的连续子数组，从当前元素 nums 开始一个新的连续子数组，即 current_sum = nums。
      
    
    
  
  
• 更新最大和：
  
  
  
  • 在每次更新 current_sum 之后，比较 current_sum 和 max_sum 的大小。如果 current_sum 大于 max_sum，就更新 max_sum 为 current_sum。
    
  
  
• 返回结果：
  
  
  
  • 遍历完整个数组后，max_sum 中存储的就是最大子序和，将其返回。
    
  
  

七: C语言代码实现

1. #include <stdio.h>
3. // 函数用于找出最大子序和
4. int maxSubArray(int* nums, int numsSize) {
5.     if (numsSize == 0) return 0;
6.     int current_sum = nums[0];
7.     int max_sum = nums[0];
9.     for (int i = 1; i < numsSize; i++) {
10.         // 判断是否更新当前连续子数组和
11.         if (current_sum + nums[i] > nums[i]) {
12.             current_sum = current_sum + nums[i];
13.         } else {
14.             current_sum = nums[i];
15.         }
16.         // 更新最大和
17.         if (current_sum > max_sum) {
18.             max_sum = current_sum;
19.         }
20.     }
22.     return max_sum;
23. }
25. int main() {
26.     int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
27.     int numsSize = sizeof(nums) / sizeof(nums[0]);
28.     int result = maxSubArray(nums, numsSize);
29.     printf("最大子序和为: %d\n", result);
30.     return 0;
31. }

复制代码

八：复杂度分析

• 时间复杂度：(O(n))，这里的 n 是数组的长度。因为只须要对数组举行一次遍历。
  
• 空间复杂度：(O(1))，只利用了常数级的额外空间。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。