53最大子数组和 动态规划和分制

 

 

 

 

 

class Solution {
public:// 时间不通过int maxSubArray_2(vector<int>& nums) {int tager_max=nums[0];int left=0;// sum_[i]   map<int,int> sum_i; // 和 索引 由于 std::map是按键排序的，最小的键在开头，最大的键在末尾：for(int right=0;right<nums.size();++right){           int current_max=0;for(int j=right;j<nums.size();++j){current_max=current_max+nums[j];//sum_i[current_max]=right;tager_max=max(tager_max,current_max);}}// map自动排序//    auto min_ = sum_i.begin()->first;//    auto max_ = (sum_i.rbegin())->first; //     cout<< " max_ " << max_//     <<" max_id " << sum_i.rbegin()->second //     <<" min_ " << min_//     <<" min_id " << sum_i.begin()->second //     <<endl;return tager_max;}// 思路错了    mapint maxSubArray3(vector<int>& nums) {// 要的不是区间长度 而是累计和 所以负数应该抛掉 而不是跟着折算最长int tager_max=nums[0];map<int,int> sum_irl; // 和 索引 由于 std::map是按键排序的，最小的键在开头，最大的键在末尾：int current_max_r=0;for(int i=0;i<nums.size();++i){              current_max_r=current_max_r+nums[i];sum_irl[current_max_r]=i;}auto max_rl = (sum_irl.rbegin())->first; auto min_rl = (sum_irl.begin())->first; tager_max=max(max_rl,max_rl-min_rl);if(max_rl==max_rl)tager_max=max_rl;// if(max_rl<=0){//     tager_max=max(max_rl,max_rl-min_rl);// }// else// {//       tager_max=max(max_rl,max_rl-min_rl);// }// map自动排序//    auto min_ = sum_i.begin()->first;//    auto max_ = (sum_i.rbegin())->first; //     cout<< " max_ " << max_//     <<" max_id " << sum_i.rbegin()->second //     <<" min_ " << min_//     <<" min_id " << sum_i.begin()->second //     <<endl;return tager_max;}//     int maxSubArray(vector<int>& nums) {int tager_max=nums[0];int pre_sum=0;for(int i=0;i<nums.size();++i){              //如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加。pre_sum=max(pre_sum+nums[i],nums[i]);tager_max=max(pre_sum,tager_max);}return tager_max;}};