首页 > 代码库 > 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