分治算法学习

思路分析：

• 先找根（最大值）分为左右子树，转化为构建最大的左右子树，很明显，这里需要用到递归
• 算法实现

#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);
}