问题描述：给定数组a[1……n],求最大子数组之和。即找出K=i<=j<=n,使得a[i]+……+a[j]之和最大 解法一：暴力枚举：三重循环 代码如下：
int maxSubArray（vector<int>& nums）{ int n=nums.size(); int ans=nums[0]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int sum=0; for(int k=i;k<=j;k++) { sum+=nums[k]; } if(ans<sum) ans=sum; } } return ans;}解法二：优化枚举：两重循环 代码如下：
int maxSubArray(vector<int>& nums) { int n=nums.size(); int ans=nums[0]; for(int i=0;i<n;i++) { int sum=0; for(int j=i;j<n;j++) { sum+=nums[j]; if(sum>ans) { ans=sum; } } } return ans; }解法三：贪心算法：一重循环 代码如下：
int maxSubArray(int* nums, int numsSize) { int sum=0,ans=nums[0]; for(int i=0;i<numsSize;i++) { sum+=nums[i]; if(ans<sum) ans=sum; if(sum<0) sum=0; } return ans;}从解法一到解法二到解法三：是时间复杂度的一步步优化，优化的方向就是减少冗余操作。多思考。
以上方法均来自七月在线的视频讲解。
新闻热点
疑难解答
