給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最小和的子數(shù)組。返回其最小和。

給出數(shù)組[1, -1, -2, 1]，返回 -3

?

本題是求最小子數(shù)組，并返回最小和。剛開(kāi)始不理解子數(shù)組的定義，后來(lái)知道了子數(shù)組必須是連續(xù)的，然后用貪心的算法解決。

class Solution {
public:
? ? /*
? ? ?* @param nums: a list of integers
? ? ?* @return: A integer indicate the sum of minimum subarray
? ? ?*/
? ? int minSubArray(vector<int> &nums) {
? ? ? ? // write your code here
? ? ? ? int s=0;//臨時(shí)的和
? ? ? ? int m=nums[0];//所求的和
? ? ? ? int n=nums.size();
? ? ? ? for(int i=0;i<n;i++)
? ? ? ? {
? ? ? ? ?s+=nums[i]; ? ? ? //相加
? ? ? ? ?if(m>s) {m=s;} ?//判斷是否比前面的小，是：賦值
? ? ? ? ?if(s>0) {s=0;} ? ? //如果加起來(lái)是個(gè)正數(shù)，那么S歸零，重新計(jì)算
? ? ? ? ?}
? ? return m;
? ? }
};

轉(zhuǎn)載于:https://www.cnblogs.com/wanrufeng/p/7689050.html

總結(jié)

以上是生活随笔為你收集整理的最小子数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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