给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
思路一：前缀和
int maxSubArray(int* nums, int numsSize){
int sum=0,ans=0,temp=nums[0],flag=1;
for(int i=1;i<numsSize;i++){
if(temp<0&&nums[i]<0&&temp<nums[i]){
temp=nums[i];
}
if(nums[i]>=0){
flag=0;
break;
}
}
if(flag==1)
return temp;
for(int i=0;i<numsSize;i++){
if(sum+nums[i]<0){
sum=0;
}
else{
sum=sum+nums[i];
if(ans<sum)
ans=sum;
}
}
return ans;
}时间复杂度O(n)，空间复杂度O(1)
分析：
本题要求最大子数组和，可考虑先求出每个元素的前缀和，再判断是否前缀和加现元素是否大于原返回值，从而得到答案。编写的过程中需考虑数组中全为负数的情况，此处先遍历完整个数组判断是否整个数组均为负数后计算前缀和，最后返回ans文章来源：https://www.toymoban.com/news/detail-625322.html
总结：
本题考察对数组的应用，前缀和的方法，利用前缀和的知识便可解决此问题。文章来源地址https://www.toymoban.com/news/detail-625322.html
到了这里，关于leetcode做题笔记53的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
