非动态规划思路:
以0为边界先将所有数据分块,然后对每个块进行遍历
找到每个块中第一个负数和最后一个负数
然后计算当前块中,左边界和最后一个负数之间的距离 与 右边界与第一个负数的距离,距离更大的就是当前块中的答案
最后在所有块中的答案中,找到最大数字,即最终答案
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int findLongestSubArray(vector<int>& nums) { // write code here int answer = 0; int left = -1; int right = -1; int negative = 0; int len = -1; int start = -1; for(int i = 0; i < nums.size() ; i++){ if(0 == nums[i]){ if(0 == i || 0 == nums[i-1] || -1 == start){ continue; } if(negative%2 == 0){ len = i - start; }else{ len = max(right-start, i - start - 1 - left); } if(len > answer){ answer = len; } left = -1; right = -1; negative = 0; len = -1; start = -1; continue; }else{ if(-1 == start){ start = i; if(nums[i] < 0 && -1 == left){ left = i; right = i; negative++; } }else if(nums[i] < 0 && -1 == left){ left = i; right = i; negative++; }else if(nums[i] < 0 && -1 != left){ right = i; negative++; } } } if(nums[nums.size()-1] != 0){ if(negative%2 == 0){ len = nums.size() - start; }else{ len = max(right-start, (int)nums.size() - 1 - left); } if(len > answer){ answer = len; } } return answer; } };