第一次提交成功

class Solution { public:int maxSubArray(vector<int>& nums) {if (nums.size() == 1) return nums[0];//int sum = -1;vector<int> submax;for (int i = 0; i < nums.size(); i++){if (sum >= 0){sum = sum + nums[i];submax.push_back(sum);}else{sum = nums[i];submax.push_back(sum);}}int max = submax[0];for (int i = 1; i < submax.size(); i++) {if (max < submax[i]) max = submax[i];}return max;} };

這里我的思路是包含當(dāng)前nums[i]的連續(xù)子數(shù)組的最大和（按序號(hào)只算ｉ左邊的），所以當(dāng)前一個(gè)nums[i-1]處的最大值是負(fù)數(shù)時(shí)，nums[i]處的最大值就是nums[i]本身，當(dāng)nums[i-1]處的最大值大于零，nums[i]處的最大值就是sum + nums[i]

對于nums中的第一個(gè)元素nums[0]，我利用初始sum = -1，在循環(huán)中進(jìn)入else把第一個(gè)位置最大值修改為nums[i]

第二次嘗試：

其實(shí)對于上面的第二個(gè)循環(huán)并不必要，完全可以在第一個(gè)中進(jìn)行。

class Solution { public:int maxSubArray(vector<int>& nums) {if (nums.size() == 1) return nums[0];//int max = nums[0]; int sum = -1;for (int i = 0; i < nums.size(); i++){if (sum >= 0){sum = sum + nums[i];}else{sum = nums[i];}if (sum > max) max = sum;}return max;} };

雖然這個(gè)sum初始化為-1看起來很巧妙，但是卻有一點(diǎn)本末倒置，畢竟這是一個(gè)求和問題，sum初始化為０要更易于理解。

第三次嘗試：先加為敬！

class Solution { public:int maxSubArray(vector<int>& nums) {int max = nums[0]; int sum = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];if (sum > max) max = sum;if (sum < 0) sum = 0;}return max;} };

判斷只有一個(gè)元素也是多余的！頂多判斷一個(gè)空數(shù)組，但是題目中說了至少有一個(gè)值。

總結(jié)

以上是生活随笔為你收集整理的LeetCode 53. 最大子序和(Maximum Subarray)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。