思路分析：
- 先找根（最大值）分为左右子树，转化为构建最大的左右子树，很明显，这里需要用到递归
- 算法实现
#include<bits/stdc++.h>
using namespace std;
int nums[1001];
void constructMaxTree(int arr[],int l,int r){
if(l>=r) {
cout<< arr[l]<<" ";
return;
}
// 找到最大值的下标
int max = -1;
int index = l;
for(int i = l;i<=r;i++){
if(max < arr[i]){
max = arr[i];
index = i;
}
}
cout<<max<<" ";
if(index==l){
cout<< "null ";
constructMaxTree(arr,index+1,r);
return;
}
constructMaxTree(arr,l,index-1);
if(index==r){
cout<< "null ";
return;
}
constructMaxTree(arr,index+1,r);
return;
}
int main(){
int i=0;
int a;
while(cin>>a){
nums[i++] = a;
}
constructMaxTree(nums,0,i-1);
}
思路分析
- 分治思想： 如果整数m在数组中为众数，那么将数组分层两半，那么m一定至少也是其中一边的众数
- 暴力：遍历数组，用map存储每个元素的出现的频率
代码
- 暴力：
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, int> mymap;
int n;
int num;
cin >> n;
int nn = n;
while (n--) {
cin >> num;
// 使用find函数查找key是否存在于map中
if (mymap.find(num) != mymap.end()) {
mymap[num]++;
} else {
mymap[num] = 1;
}
}
// 找出mymap中value最大值，比较n/2
map<int, int>::iterator it = mymap.begin();
map<int, int>::iterator maxit;
int max = -1;
while (it != mymap.end()) {
if (max < it->second) {
max = it->second;
maxit = it;
}
++it;
}
if (max > nn / 2) {
cout << maxit->first;
}
return 0;
}
思路分析
-
一个数的数组[a]的最大和的连续的子数组是他自己[a]
-
两个数的[a,b]数组的最大和的连续的子数组是max([a,b],[b])
-
......
-
所以推出：求一个数组的最大和的连续子序列[a,b,c,d,e,f]，可以类推为求，这个数组的少一元素的子数组的最大和子序列（考虑要不要加入这个元素）max [a,b,c,d,e],[a,b,c,d,e,f]
-
上代码
#include<bits/stdc++.h>
using namespace std;
int findMax(vector<int> v){
int max = 0;
int res = max;
for(int i=0;i<v.size();i++){
if(max+v[i] <= v[i]){
max = v[i];
}else{
max = max+v[i];
}
if(max > res){
res = max;
}
}
return res;
}
int main() {
vector<int> v;
int n;
cin >> n;
int val;
for(int i=0;i<n;i++){
cin >> val;
v.push_back(val);
}
cout<<findMax(v);
}