已知一个整数序列，求其和最大的最长连续子序列。请你帮我用c++分别设计三种代码。第一种算法时间复杂度不高于O(n3），第二种算法时间复杂度不高于O（n2），第三种算法时间复杂度为O（n））

第一种算法：

暴力枚举所有可能的子序列，计算它们的和并记录最大值，时间复杂度为O(n3)。

代码如下：

int maxSubArray(int* nums, int numsSize){
int maxSum = INT_MIN;
for(int i=0; i<numsSize; i++){
for(int j=i; j<numsSize; j++){
int sum = 0;
for(int k=i; k<=j; k++){
sum += nums[k];
}
maxSum = max(maxSum, sum);
}
}
return maxSum;
}

第二种算法：

使用动态规划，定义状态dp[i]表示以第i个元素结尾的最大子序列和。则有状态转移方程：dp[i] = max(dp[i-1]+nums[i], nums[i])。时间复杂度为O(n2)。

代码如下：

int maxSubArray(int* nums, int numsSize){
int dp[numsSize];
dp[0] = nums[0];
int maxSum = dp[0];
for(int i=1; i<numsSize; i++){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}

第三种算法：

使用Kadane算法，定义变量curSum表示当前子序列和，maxSum表示最大子序列和。从左往右遍历数组，每次加上当前元素，如果curSum变成负数，则将curSum重置为0，表示重新开始计算子序列和。时间复杂度为O(n)。

代码如下：

int maxSubArray(int* nums, int numsSize){
int curSum = 0, maxSum = INT_MIN;
for(int i=0; i<numsSize; i++){
curSum += nums[i];
maxSum = max(maxSum, curSum);
curSum = max(curSum, 0);
}
return maxSum;
}