매일 한 문제 - 검지 Offer 42.연속 서브그룹의 최대 및

제목 정보

시간: 2019-06-30

제목 링크: 리코더

tag: 동적 기획

난이도: 간단

제목 설명: 하나의 정형 수조를 입력하면 수조에 양수도 있고 음수도 있다.그룹 중의 하나 또는 연속된 여러 개의 정수가 하나의 하위 그룹을 구성한다.모든 하위 그룹의 최대 값을 구하십시오.요구 시간의 복잡도는 O(n)이다.

예:

  : nums = [-2,1,-3,4,-1,2,1,-5,4]
  : 6
  :       [4,-1,2,1]     ，  6。

프롬프트

1. 1 <= arr.length <= 10^5
2. -100 <= arr[i] <= 100

문제풀이의 방향

난점
흔히 볼 수 있는 해법
시간 복잡도
공간 복잡도
폭력 수색
O(N^2)
O(1)
분치사상
O(NlogN)
O(logN)
동적 기획
O(N)
O(1)
구체적 사고방식
동적 기획

상태 정의: 동적 기획 목록 dp를 설정하고 dp[i]]는 요소nums[i]를 끝으로 하는 연속 서브 그룹이 가장 크고

전이 방정식: 만약에 dp[i-3-1]≤0이면 dp[i-3-1]가 dp[i]에 마이너스 공헌을 하는 것을 의미한다. 즉, dp[i-3-1]+nums[i]는nums[i] 자체보다 크다.

dp[i-1]>0일 때 dp[i]=dp[i-1]+nums[i]

를 실행한다

dp[i-1] <0시 dp[i]=nums[i]

실행

초기 상태: dp[0] =nums[0]

코드

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int sum = nums[0];
        int former = 0;//    dp[i-1]  ，  dp[0]  ，    dp[-1]=0
        int cur= nums[0];//    dp[i]  
        for(int num: nums){
            if(former <= 0){
                cur = num;
            }
            if(former > 0){
                cur = former + num;
            }//        cur = Math.max(former,0) + num;                
            former = cur;
            sum = Math.max(sum,cur);
        }
        return sum;
    }
}

복잡성 분석:

시간 복잡도 O(N): 선형 스트리밍 그룹nums로 결과를 얻을 수 있으며 O(N) 시간을 사용합니다.

공간 복잡도 O(1): 상수 크기의 추가 공간을 사용합니다.

기타 우수한 해답

문제풀이의 방향
분리법, 우리는 수조nums를 중간 위치 (mid) 로 왼쪽 (left) 오른쪽 (right) 두 부분으로 나눈다.그럼 레프트=nums[0]...nums[m - 1]와 right = nums[m + 1]...nums[n-1]
최대 하위 시퀀스 및 위치는 다음 세 가지입니다.

중간원소nums[m]를 고려하여 좌우 두 부분을 뛰어넘는다. 여기서 중간원소부터 왼쪽으로 접두사를 구하면 가장 크고 오른쪽으로 접두사를 구하면 가장 크며 연속성을 유지한다.

중간 원소를 고려하지 않고 가장 큰 서열과 왼쪽 부분에 나타나 왼쪽 부분의 가장 큰 서열과

중간 원소를 고려하지 않고 가장 큰 서열과 오른쪽 부분에 나타나 오른쪽 부분의 가장 큰 서열과

코드

class MaximumSubarrayDivideConquer {
  public int maxSubArrayDividConquer(int[] nums) {
      if (nums == null || nums.length == 0) return 0;
      return helper(nums, 0, nums.length - 1);
    }
    private int helper(int[] nums, int l, int r) {
      if (l > r) return Integer.MIN_VALUE;
      int mid = (l + r) >>> 1;
      int left = helper(nums, l, mid - 1);
      int right = helper(nums, mid + 1, r);
      int leftMaxSum = 0;
      int sum = 0;
      // left surfix maxSum start from index mid - 1 to l
      for (int i = mid - 1; i >= l; i--) {
        sum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, sum);
      }
      int rightMaxSum = 0;
      sum = 0;
      // right prefix maxSum start from index mid + 1 to r
      for (int i = mid + 1; i <= r; i++) {
        sum += nums[i];
        rightMaxSum = Math.max(sum, rightMaxSum);
      }
      // max(left, right, crossSum)
      return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
    }
}