博文视点微博上提出的两个问题

原本打算在新浪长微博上发，但是尼玛总提示敏感信息，我了个去，只好该在这里发了

ps:微博@骑猪猪吹泡泡

题目一主要思路：把原问题转化成求两个小集合的子集和的问题，遍历原数组，为保持原数据不造破坏，正负数置于另外申请的空间，把负数转成正数存储，同时判断原数据是否有0元素的存在。将分开的正负数（现在变成两组正数集合假设为A，B）快排让其有序，同时进行优化，剔除不会参与求子集和的元素，也即，A中存在元素比B中所有元素的和都大，显然这样的元素无效，目的是尽可能减少元素个数以减少穷举子集和的次数。然后选取元素个数少的集合来求子集和sum0，然后在另一集合中判断是否存在子集和等于sum0，同时在进入另一集合判断时仍就做优化处理，剔除集合中大于sum0的元素。总之就是尽量减少参与计算子集和的元素个数
代码如下

#include "stdafx.h"#include <iostream>template<class type>class queue_node{public:queue_node(type value){data = value;next = NULL;sorted_prior = NULL;sorted_next =NULL;}~queue_node(){}type data;queue_node* next;queue_node* sorted_prior;queue_node* sorted_next;};template<class type>class queue{public:queue(){head = NULL;tail = NULL;sorted_list = NULL;length = 0;}~queue(){if( 0 ==length)return;queue_node<type> *p = head;queue_node<type> *q = p->next;while(p){delete p;p = q->next;}}//添加新结点void push_back(type data);//移除队头元素void pop();//获取队头元素，成功返回true，同时value的值为队头元素值bool get_head(type& value) const;  //获取队列最大元素bool get_max_value(type& value) const;//获取队列长度inline size_t get_length() const;private:inline void rm_sorted_node(queue_node<type>* rm_node);inline void add_sorted_node(queue_node<type>* add_node);private:queue_node<type>* head;queue_node<type>* tail;queue_node<type>* sorted_list;size_t length;};template <class type> void queue<type>::push_back(type data){queue_node<type> *node = new queue_node<type>(data);if (!length)head =tail = node;else{tail->next = node;tail = tail->next;}++length;add_sorted_node(node);}template <class type> void queue<type>::pop(){queue_node<type> *node = head;if (node){rm_sorted_node(node);head = head->next;delete node;--length;}if( !length)head = tail = NULL;}template <class type> inline size_t queue<type>::get_length() const{return this->length;}template <class type> bool queue<type>::get_head(type& value) const{if(!get_length())return false;value = head->data;return true;}template <class type> bool queue<type>::get_max_value(type& value) const{if(sorted_list)value = sorted_list->data;elsereturn false;return true;}template <class type> inline void queue<type>::rm_sorted_node(queue_node<type>* rm_node){if(!rm_node->sorted_prior){sorted_list = rm_node->sorted_next;if(sorted_list){sorted_list->sorted_prior = NULL;}return;}rm_node->sorted_prior->sorted_next = rm_node->sorted_next;if(rm_node->sorted_next)rm_node->sorted_next->sorted_prior = rm_node->sorted_prior;}template <class type> inline void queue<type>::add_sorted_node(queue_node<type>* add_node){if(!sorted_list){sorted_list = add_node;return;}queue_node<type>* temp_node;temp_node = sorted_list;while(temp_node->sorted_next &&(temp_node->data > add_node->data))temp_node = temp_node->sorted_next;if(!temp_node->sorted_next &&(temp_node->data > add_node->data)){add_node->sorted_prior = temp_node;temp_node->sorted_next = add_node;}else{add_node->sorted_next = temp_node;add_node->sorted_prior = temp_node->sorted_prior;if(temp_node->sorted_prior)temp_node->sorted_prior->sorted_next = add_node;elsesorted_list = add_node;temp_node->sorted_prior = add_node;}}using namespace std;int _tmain(int argc, _TCHAR* argv[]){queue<int> my_queue;int a[] = {213,435,32,34,54,65,2,776,32,65,21,43,23,55,76,23,76,88,43,12};for(int i=0;i<(sizeof(a)/sizeof(int));++i)my_queue.push_back(a[i]);int max = 0;my_queue.get_max_value(max);cout<<"最大值为："<<max<<endl;for(int i=0;i<(sizeof(a)/sizeof(int)); ++i){int value =0;my_queue.get_head(value);std::cout<<"移除元素"<<value<<endl;my_queue.pop();my_queue.get_max_value(max);cout<<"此时队列最大值为："<<max<<endl;}return 0;}