下面的代码，如果存在多个最大的子序列，则只返回最前面的。

如果数组全为负数，比如-3, -2, -1, -8， 程序返回 -1，起始，终止位置都是2


int MaxNumber(int* A){
    int nStart = A[0];
    int nAll = A[0];
    int tmpStart = 1;
    int si = 1 ,    ei = 1;
    for( int i = 1; i < n; i++)
    {
      

书中解法三用数组来对树进行BFS，比较适合在比赛中使用，如果使用队列的话，当数据规模比较大的时候，频繁的进队列，出队列还是很耗时的。 比较经典的“聪明的打字员”一题，就是BFS搜索，但是数据规模比较大，用队列的话很容易超时，参考PKU1184.

扩展问题一、二是按深度从下到上遍历二叉树，从左向右或者从右向左。
我们可以在开始根节点遍历的时候，每层遍历结束之后，存放一个 NULL 作为层与层之间的分割，当整棵树遍历完之后，再从后向前遍历数组，遇到 NULL 表示当前层结束，这样就可以实现按深度从下到上

扩展问题2： 判断给出前序与中序序列是否合理

递归算法实现，分别遍历左右子树，递归中迭代查找左右子树的长度，类似于书中的方法。

#include <iostream>
#include <string>

using namespace std;

bool valid = true;

// 在中序遍历串的start end之间找前序串中的某个节点

//needle为前序串里面的某个节点， haystack 为中序遍历串
inline int find(char needle, const char* haystack, int start, int end )
{
    const char*

#include <stack>
#include <algorithm>
using namespace std;

struct Node
{
    bool _visited;

    Node* left;
    Node* right;
    int maxLeft;
    int maxRight;

    Node()
    {
        _visited = false;
   

扩展1：链表1 步长为1， 链表2步长为2 ，如果有环且相交则肯定相遇，否则不相交

list1 head: p1

list2 head: p2

while( p1 != p2 && p1 != NULL && p2 != NULL )

{

      p1 = p1->next;

      if ( p2->next )

         p2 = p2->next->next;

      else

    

这个问题，我在面试中也问过，几乎所有的candidates都能给出解法一，至于解法二，并没有新意，读过STL源代码的人都知道：

STL里面的rotate函数<algorithm>，就是用这种方法实现的

template<class _BidIt> inline
    void _Rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,   bidirectional_iterator_tag)
    {   
        std::reverse(_First, _Mid);
  

Type candidate1 ;
Type candidate2;
Type candidate3;

void Find(Type* ID, int N)
{
    int nTimes1 = 0 ;
    int nTimes2 = 0 ;
    int nTimes3 = 0 ;
    int i;

    for( i = 0; i < N; i++)
    {
        if (nTimes1 == 0)
        {
    

把两个整数 A, B 异或, 然后又回归到判断 1 的个数

int Count( int a, int b)
{
    int num = 0;
    int v = a ^ b;
    while(v)
    {
       v &= (v-1);
       num++;
    }
    return num;
};