一、360面试题1、求一个序列的最长上升子序列（不降）方法一：动态规划:，其中num[]数组中存放的是0~i的最长子序列长度#includeiostream #define MAX 100 using namespace std; //时间复杂度为O(n^2) int LIS(int a[], int n) { int num[MAX]; //用来存放对应点的最长子序列长度 int maxlen = 0; //存储最大长度 for (int i = 0; i n; i++) { num[i] = 1; //求0~i-1的最长子序列长度 for (int j = 0; j i; j++) { if (a[j]=a[i] (num[j] + 1) num[i]) { num[i] = num[j] + 1; } } if (num[i] maxlen) { maxlen = num[i]; } } return maxlen; }方法二：采用二分法对上述算法进行优化，其中d[]数组保存的是0~i的最长上升子序列#includeiostream #includealgorithm #define MAX 100 using namespace std; int LIS2(int a[], int n) { int d[MAX]; int maxlen = 0; d[0] = a[0]; for (int i = 1; i n; i++) { if (a[i] = d[maxlen]) { d[++maxlen] = a[i]; } else { int j = lower_bound(d+1,d+maxlen+1,a[i]) - d; d[j] = a[i]; } } return maxlen + 1; }2、快速排序#includetime.h #include stdio.h #include stdlib.h #define N 10000 #define MAX 100000000 void swap(int *a,int *b){ int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int start, int end){ swap(arr[start],arr[end]); int value = arr[end]; int index = start; for(int i=start;iend;++i){ if(arr[i] value){ swap(arr[index++],arr[i]); } } swap(arr[index],arr[end]); return index; } void quickSort(int arr[],int sta