[Offer 에세이] 42 연속 하위 배열의 최대 및 동적 계획

  • 42 연속 하위 배열의 최대 및 - 소스: 리코더 링크:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof정수 그룹을 입력하십시오. 그룹 중 하나 또는 여러 개의 정수가 하위 그룹을 구성합니다.모든 하위 그룹의 최대 값을 구하십시오.요구 시간의 복잡도는 O(n)이다.
  •   1:
    
      : nums = [-2,1,-3,4,-1,2,1,-5,4]
      : 6
      :       [4,-1,2,1]     ,  6。
    
    :【c++】 : , i i , nums, i i-1 nums[i], nums[i] ( i-1 ), 。
    // c++
    class Solution {
         
    public:
        int maxSubArray(vector<int>& nums) {
         
            //     
            int num = 0,max = nums[0];
            for(int i = 0;i<nums.size();++i){
         
                if(nums[i]< num + nums[i]){
         
                    nums[i] +=num;
                }
                num = nums[i];
                if(max < nums[i])
                    max = nums[i];
            }
            return max;
        }
    };
    
    # python3
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            for i in range(1,len(nums)):
                nums[i] += max(nums[i-1],0)
            return max(nums)
    

    좋은 웹페이지 즐겨찾기