Lintcode-贪心-最大子数组和最小子数组

点此进入最大子数组题目

点此进入最小子数组题目

最大子数组和最小子数组解题思路和代码都是相似的，无非是一个大于号，一个小于号。所以主要介绍最大子数组的解题思路和过程。

解题思路：首先要注意这里的子数组是连在一起的，如一组数组[1,2,3,4,5,6]，[1,2,3]是它的子数组,但[1,2,5]不是。然后题目要求是求元素和最大的子数组，这个子数组只是要求元素是位置是连在一起的，但是数量不是一定的。所以我用了一个比较简单的方法，就是将子数组的数量从1，2，3一直到n顺序求子数组，然后将和最大的数字返回。

解题过程：给定一个数组，得到长度l。从一开始循环到l，表示数组长度从一开始；然后循环内循环，i=I,循环到l，求得最大的子数组和，赋值给max.，最后返回max。

代码实现：

int maxSubArray(vector<int>&nums)\最大子数组代码

 {

int M=nums[0],l=nums.size();

for(int I=0;I<l;I++)

{

       int A=0；

       for(int i=I;i<l;i++)

       {

           A+=nums[i];

           if(A>=M)

           {

               M=A;

           }

       }

       

   }

   return M;

}

intminSubArray(vector<int> &nums)\最小子数组代码

 {

       // write your code here

       int M=nums[0],l=nums.size();

   for(int I=0;I<l;I++)

   {

       int A=0;

       for(int i=I;i<l;i++)

       {

           A+=nums[i];

           if(A<=M)

           {

               M=A;

           }

       }

   }

   return M;

   }

注意事项：子数组位置一定要连在一起；然后这个简单的题目也没什么要注意的，也没多少坑来坑大家。

个人理解：这道题也只是一个简单的贪心算法，也很适合新手来接触贪心算法。