今天份做題：
前幾天在看資料結構的時候剛好看到一個復雜度為O（n）的演算法，分享于下，
解題思路 ：
該題的主要難度為如何保證子陣列在陣列中是最大的，因此我們從陣列中的第一個元素開始遍歷，如果當前子陣列累積和為負，那我們就舍棄當前子陣列中所有元素，而每從主陣列讀取記錄一個新的元素，當前主陣列就與Sum進行比較，小于無操作，大于則進行賦值操作，實作代碼如下：
代碼實作 ：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum,i,j;
for(i=0;i<sizeof(nums) / sizeof(int);i++)
{
j+=nums[i];
if(j<0)
{
j=0;
}else if(j>sum)
{
sum=j;
}
}
printf("%d",sum);
}
};經過朋友提醒，沒有考慮某些極端情況（nums中所有的數都是負數），考慮到這個情況，可以在程式最后加入一個判斷
if(sum=0)
{
sum=sum[0];
for(i=1;i<sizeof(nums) / sizeof(int)-1;i++)
{
if(sum<nums[i])
{
sum=nums[i];
}
}
}再次遍歷一次陣列，找到那個最大的負數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413295.html
標籤：其他