最大子序和题目——动态规划/贪心算法办理
目录一：题目描述
二：办理思路1——动态规划思想
三：C 语言代码实现
四：复杂度分析
五：办理思路2——贪心算法思想
六：具体步骤
七: C语言代码实现
八：复杂度分析
一：题目描述
最大子序和题目指的是在一个整数数组里，找出一个具有最大和的连续子数组（子数组最少包含一个元素），然后返回其最大和。
例如，对于数组 [-2,1,-3,4,-1,2,1,-5,4]，其连续子数组 的和最大，为 6。
二：办理思路1——动态规划思想
[*]界说一个数组 dp，此中 dp 代表以第 i 个元素结尾的连续子数组的最大和。
[*]状态转移方程：dp = max(dp + nums, nums)。也就是说，以第 i 个元素结尾的连续子数组的最大和，要么是把第 i 个元素加入到以第 i - 1 个元素结尾的连续子数组中，要么是第 i 个元素单独作为一个子数组。
[*]最终的最大子序和就是 dp 数组中的最大值。
三：C 语言代码实现
#include <stdio.h>
// 函数用于找出最大子序和
int maxSubArray(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int dp;
dp = nums;
int max_sum = dp;
for (int i = 1; i < numsSize; i++) {
// 状态转移方程
if (dp + nums > nums) {
dp = dp + nums;
} else {
dp = nums;
}
// 更新最大和
if (dp > max_sum) {
max_sum = dp;
}
}
return max_sum;
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int numsSize = sizeof(nums) / sizeof(nums);
int result = maxSubArray(nums, numsSize);
printf("最大子序和为: %d\n", result);
return 0;
} 四：复杂度分析
[*]算法的时间复杂度为 (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语言代码实现
#include <stdio.h>
// 函数用于找出最大子序和
int maxSubArray(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int current_sum = nums;
int max_sum = nums;
for (int i = 1; i < numsSize; i++) {
// 判断是否更新当前连续子数组和
if (current_sum + nums > nums) {
current_sum = current_sum + nums;
} else {
current_sum = nums;
}
// 更新最大和
if (current_sum > max_sum) {
max_sum = current_sum;
}
}
return max_sum;
}
int main() {
int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int numsSize = sizeof(nums) / sizeof(nums);
int result = maxSubArray(nums, numsSize);
printf("最大子序和为: %d\n", result);
return 0;
} 八：复杂度分析
[*]时间复杂度：(O(n))，这里的 n 是数组的长度。因为只须要对数组举行一次遍历。
[*]空间复杂度：(O(1))，只利用了常数级的额外空间。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]