华为OJ相关算法

1、合唱队问题
给定一个身高数组，从里面抽出若干人之后，使之保持身高由小到大，再从大到小的合唱队队形，求出至少出队的人数！
解题思路：必须得考虑清楚每一个位置左边递增的人数和右边递减的人数，两者的最大和即为最长的合唱队人数。所以可以两次遍历数组，求最长递增（减）子序列即可。关于最长递增子序列的问题我们已经很熟悉了。下面直接码上代码已经相关过程解析。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
//输入参数：合唱队的总人数和身高
//输出参数：出队的最少人数
int chorusSolute(int a[],int n){
    //1.对于任意的当前i个位置，从左往右遍历，找到i之前的最长递增子序列
    int l[10];
    fill_n(l,10,1);  //初始化为1
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[i]>a[j]&&l[i]>l[j]+1){
                l[i]=l[j]+1;
            }   
        }
    }
    int r[10];
    fill_n(r,10,1);//初始化为1
    for(int i=n-2;i>=0;i--){
        for(int j=n-1;j>i;j--){
            if(a[j]<a[i]&&r[i]>r[j]+1){
                r[i]=r[j]+1;
            }
        }
    }
    int sum=1;
    for(int i=0;i<n;i++){
        if(sum<l[i]+r[i])
            sum=l[i]+r[i];
    }
    return n-sum+1;
}
int main(){
    int a[]= { 186,186 ,150, 200, 160, 130, 197, 200 };
    int m=chorusSolute(a,8);
    cout<<m<<endl;
    system("pause");
    return 0;
}

2、 Candy问题
有一排学生，随机排好队，每个学生的成绩不一样，根据成绩来发糖果，保证每个人至少有一颗糖果，成绩较高的人获得的糖果比两边的人获得糖果多，问至少需要发放多少糖果？
解题思路：首先要创建一个数组用来保存每个人的糖果数目，然后先从左往右遍历，在从右往左遍历。代码解析如下所示：

#include<iostream>
#include<string>
#include<algorithm>
#include<numeric>
using namespace std;
int candy(int a[],int n){
    //1.创建数组保存每个人的糖果数目,初始状态每个人至少有一个糖果
    int candyNum[100];
    memset(candy,0,100);
    //2.从左往右扫描，确定后一个比前一个多的时候就增加一个糖
    for(int i=1,inc=1;i<n;i++){
        if(a[i]>a[i-1]){
            candyNum[i]=max(inc++,candyNum[i]);
        }else{
            inc=1;
        }
    }
    for(int i=n-2,inc=1;i>=0;i--){
        if(a[i]>a[i+1]){
            candyNum[i]=max(inc++,candyNum[i]);
        }else{
            inc=1;
        }
    }
    int sum=accumulate(candyNum,candyNum+n,n);
    return num;
}