C++实现最大子数组和算法 - Kadane算法

{"title":"C++实现最大子数组和算法 - Kadane算法","description":"本文使用C++语言实现了Kadane算法，用于计算给定一维数组中所有子数组的最大和。代码简洁易懂，并附有详细解释说明。","keywords":"C++，最大子数组和，Kadane算法，动态规划，子数组求和","content":"#include <iostream>\n#include <vector>\n#include <limits>\n\nint maxSubArraySum(std::vector<int>& nums) {\n int maxSum = std::numeric_limits<int>::min();\n int currentSum = 0;\n \n for (int i = 0; i < nums.size(); i++) {\n currentSum += nums[i];\n if (currentSum > maxSum) {\n maxSum = currentSum;\n }\n if (currentSum < 0) {\n currentSum = 0;\n }\n }\n \n return maxSum;\n}\n\nint main() {\n std::vector<int> nums = {1, -2, 3, 10, -4, 7, 2, -5};\n int maxSum = maxSubArraySum(nums);\n std::cout << maxSum << std::endl;\n \n return 0;\n}\n\n该代码使用了动态规划的思想，通过遍历数组，依次计算以当前元素为结尾的子数组的和，同时更新最大和。如果当前和为负数，则将当前和重置为0，因为负数对后续和的计算只会产生负面影响。最后返回计算得到的最大和。\n\n输出结果为：18"}