1. 连续子数组的最大和
思路一：从头开始遍历，设置两个数，一个记录当前序列和，一个记录最大序列和。如果当前序列和小于等于0，说明前面的序列没有用，令当前序列和为下一个数字，如果大于0，就继续往上加，再与最大序列和做对比。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int len=array.size();
        if(len<=0) return 0;
        int cur=0;
        int res=0x80000000;//最小负数
        for(int i=0;i<len;i++)
        {
            if(cur<=0)
                cur=array[i];//小于等于0，舍去记录的序列
            else
            {
                cur+=array[i];//否则序列加一个数
            }
            res=max(res,cur);//比较
        }
        return res;  
    }
};

思路二：动态规划。当i=0或f(i-1)<=0时，f(i)=pData[i]；当i≠0且f(i-1)>0时，f(i)=f(i-1)+pData[i]，我们要求的就是max（f[i]） 0<=i<=n;其实动态规划与思路一思想是一样的。

2. 1-n整数中出现1的次数
思路一：暴力，另写一个函数计算每个数字出现1的次数，然后遍历1-n。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n<1) return 0;
        int count=0;
        for(int i=1;i<=n;i++)
        {
            int temp=i;//借助一个temp，直接用i的话i会一直为0
            while(temp)
            {
                if(temp%10==1)
                    count++;
                temp=temp/10;
            }
        }
        return count;     
    }
};

思路二：以21345为例子，将其分为1-1345和1346-21345两个部分。先看1346-21345中出现的次数，分两种情况：第一种情况，计算万位的1，出现了10000次，注意次数如果21345是小于19999的数字，那么就不会出现10000次，而是x-10000+1次；第二种情况，分析1除了最高位之外的其他四位数中的情况，由于最高位是2，我们可以再分为，1346-11345与11345-21345两段。每一段剩下的四位数字中，选择其中一位是1，其余三位可以从0-9这十个数字中任意选择。根据排列组合，次数是2×4×10^3.再看1-1345，递归即可。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n<=0)
            return 0;
        char strN[50];
        sprintf(strN,"%d",n);//转换成字符串
        return NumberOf1(strN);    
    }
    int NumberOf1(const char* strN)
    {
        if(!strN||*strN<'0'||*strN>'9'||*strN=='\0')
            return 0;//结束条件
        int first=*strN-'0';//最高位
        unsigned int length=static_cast<unsigned int>(strlen(strN));
        if(length==1&&first==0)
            return 0;
        if(length==1&&first>0)
            return 1;//0-9
        int numFirstDigit=0;//最高位
        if(first>1)
            numFirstDigit=pow(10,length-1);
        else if(first==1)
            numFirstDigit=atoi(strN+1)+1;//10000-12345
        int numOtherDigits=first*(length-1)*pow(10,length-2);//剩余位数排列组合
        int numRecursive=NumberOf1(strN+1);//递归
        return numFirstDigit+numOtherDigits+numRecursive;       
    }
};

3.数字序列中某一位的数字
思路：以第1001为为例子，序列前十位是0-9这十个数字，1001>10，从991开始找两位数，两位数一共180，991>180，所以第991位在所有的两位数之后，991-190=881；三位数一共2700位，由于881<2700，所以第881位是某三位数中的一位。由于811=270×3+1，可得811位是100+270这个数的中间一位，也就是7.

 int digitAtIndex(int index)
 {
     if(index==0)
     return -1;
     int digits=1;
     while(true)
     {
         int numbers=countOfIntegers(digits);//计算m位的数字有多少个
         if(index<numbers*digits)
         {
             return digitAtIndex(index,digits);
         }
         index-=digits*numbers;//减去前面的位数
         digits++;
     }
     return -1;
 }
 int countOfIntegers(int digits)//计算m位的数字个数
 {
     if(digits==1)
     return 10;
     int count=(int)pow(10,digits-1);
     return 9*count;
 }
 int digitAtIndex(int index,int digits)
 {
     int number=beginNumber(digits)+index/digits;
     int indexFromRight=digits-index%digits;
     for(int i=1;i<indexFromRight;i++)
     {
         number/=10;
     }
     return number%10;
 }
 int beginNumber(int digits)
 {
     if(digits==1)
     return 0;
     return (int)pow(10,digits-1);
 }