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