给定一个int数组,请使用C++找出和最大的连续子数组
时间: 2023-05-14 19:05:19 浏览: 97
可以使用Kadane算法来解决这个问题,该算法的时间复杂度为O(n)。以下是示例代码:
```c
#include <stdio.h>
int maxSubArray(int* nums, int numsSize){
int maxSum = nums[0];
int curSum = nums[0];
for (int i = 1; i < numsSize; i++) {
curSum = curSum > 0 ? curSum + nums[i] : nums[i];
maxSum = maxSum > curSum ? maxSum : curSum;
}
return maxSum;
}
int main() {
int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int maxSum = maxSubArray(nums, numsSize);
printf("The maximum sum of contiguous subarray is %d\n", maxSum);
return 0;
}
```
输出结果为:
```
The maximum sum of contiguous subarray is 6
```
该算法的思路是遍历整个数组,维护两个变量:当前连续子数组的和curSum和最大连续子数组的和maxSum。对于每个元素,如果curSum大于0,则将其加入curSum中,否则将curSum更新为当前元素。每次更新maxSum时,比较curSum和maxSum的大小,取较大值作为新的maxSum。最终返回maxSum即可。