今日头条第二道编程题

#include <iostream>
#include <vector>
#include <stack>
#include <time.h>
#include <algorithm>
using namespace std;
int vecSum(vector<int> &num, int i, int j)//计算num[i]到num[j]的和 
{
	int sum=0;
	for (int k = i; k <= j; k++) {
		sum += num[k];
	}
	return sum;
}
int incr_stack(vector<int> &num) {//单调栈实现 
	stack<int> s;
	int sum = 0;
	int maxSum = INT_MIN;
	int n = num.size();
	for (int i = 0; i<n; i++) {
		if (s.empty() || num[i] >=num[s.top()]) {
			s.push(i);
		}
		else {
			while (!s.empty() && num[s.top()] >=num[i]) {
				int top = s.top();
				s.pop();
				int tmp=s.empty()? vecSum(num, 0, i-1) : vecSum(num, s.top()+ 1, i - 1);
				int curSum = num[top]*tmp;
				maxSum = max(curSum, maxSum);
			}
			s.push(i);
		}
	}
	while (!s.empty()) {
		int top = s.top();
		s.pop();
		int tmp=s.empty()? vecSum(num, 0, n-1): vecSum(num, s.top()+ 1, n - 1);
		int curSum =  num[top]*tmp;
		maxSum = max(curSum, maxSum);
	}
	return maxSum;
}
int enum_method(vector<int> &num) {//穷举方法，用于测试 
	int n = num.size();
	int maxSum = INT_MIN;
	vector<int> tmp;
	for (int i = 0; i<n; ++i) {
		for (int j = i; j<n; ++j) {
			tmp.clear();
			for (int k = i; k <= j; ++k) {
				tmp.push_back(num[k]);
			}
			sort(tmp.begin(), tmp.end());
			int curSum = tmp[0] * vecSum(tmp, 0, tmp.size() - 1);
			maxSum = max(curSum, maxSum);
		}
	}
	return maxSum;
}
vector<int> getRandomArray(int len) {//随机产生数组 
	vector<int> res;
	if (len<0)
		return res;
	res.reserve(len);
	srand((unsigned)time(NULL));  
	for (int i = 0; i<len; i++) {
		res.push_back(rand() % 100);
	}
	return res;
}
void printArray(vector<int> arr) {//用于测试 

	for (int i = 0; i<arr.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
int main()
{
	bool flag=true;
	for(int i=1;i<200;i++){
		vector<int> num = getRandomArray(i);
		//printArray(num);
		int res1=enum_method(num);
		int res2=incr_stack(num);
		if(res1!=res2){
			flag=false;
			break;
		}	 
	}
	if(flag)
		cout<<"true"<<endl;
	else
		cout<<"false"<<endl;
}