問題描述：給定數組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;}從解法一到解法二到解法三：是時間復雜度的一步步優化，優化的方向就是減少冗余操作。多思考。
以上方法均來自七月在線的視頻講解。
新聞熱點
疑難解答
