溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
題意：
根據給定的數組，查找和最大的字串。
使用 "Kadane算法"查找最大和字串。
解題：
1）定義變量Max來保存最大和。定義sum來保存中間值的和。
2）數組連續幾個值的和如果為負數，也就意味著再往負數上加正數就沒有意義了，加上的和肯定不會大于加上數的值。此時重新開始計算聯系元素和即可。
3）如果數組為全負元素，那么取出最大值即可。
if ( sum <= 0 )
{
sum = 0;
}
作用保證重新計數時，是從零開始的。
if ( sum <= 0 )
{
sum = *( nums + cnt );
}
沒有置零而是置為當前值，是為了防止全負數組時，能把最大的值存入Max變量中。
Max起始置為INT_MIN保證了int型的任何負數都可存入。int maxSubArray(int* nums, int numsSize)
{
int cnt = 0;
int max = INT_MIN;
int sum = 0;
for ( cnt = 0; cnt < numsSize; cnt++ )
{
if ( sum <= 0 )
{
sum = 0;
}
sum = sum + *( nums + cnt );
if ( sum <= 0 )
{
sum = *( nums + cnt );
}
if ( sum > max )
{
max = sum;
}
}
return max;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
