首页 > 代码库 > Colidity-- MaxDoubleSliceSum
Colidity-- MaxDoubleSliceSum
左右两次遍历,记录以当前元素结尾的左边最大字串和以及右边最大字串和,最后遍历,相加
1 // you can also use includes, for example: 2 // #include <algorithm> 3 #include <vector> 4 #include <algorithm> 5 int solution(vector<int> &A) { 6 // write your code in C++98 7 if(A.size()==3) { 8 return 0; 9 }10 int len = A.size();11 A[0]=0;12 A[len-1]=0;13 vector<int> leftVec(A);14 vector<int> rightVec(A);15 16 for(int i=1;i<len-1;i++) {17 leftVec[i] = max(leftVec[i],leftVec[i]+leftVec[i-1]);18 rightVec[len-1-i] = max(rightVec[len-1-i],rightVec[len-1-i]+rightVec[len-i]);19 }20 int res = A[1];21 for(int i=1;i<len-1;i++) {22 int tmp = leftVec[i]+rightVec[i]-A[i]*2;23 if(tmp>res) {24 res = tmp;25 }26 }27 return res;28 }
Colidity-- MaxDoubleSliceSum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。