[Leetcod 동적 계획] 하위 배열 의 최대 와 같은 문제

53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array  [−2,1,−3,4,−1,2,1,−5,4] , the contiguous subarray  [4,−1,2,1]  has the largest sum =  6 .
이 문 제 는 '연속 서브 배열 의 최대 화' 가 검 지 오 피 스, 프로 그래 밍 의 아름다움 에 있어 서 모두 있 으 며, 지금까지 참가 한 면접 에서 두 번 이나 물 어 본 적 이 있어 그 중요성 을 알 수 있다.사고방식: A [i] 이전의 연속 단락 을 sum 이 라 고 가정한다.A [i] 는 i 로 끝 나 는 연속 서브 배열 의 최대 합 이다.쉽게 생각 할 수 있 습 니 다. 1. sum > = 0 이면 A [i] 와 연결 하여 새로운 sum 을 구성 할 수 있 습 니 다.A [i] 가 아무리 크 더 라 도 하나의 정 수 를 더 하면 더 클 것 이기 때문에 새로운 candidate 를 형성 할 수 있 습 니 다.2. 반대로 sum < 0 이 라면 A [I] 와 연결 할 필요 가 없다.A [i] 가 아무리 작 아 도 마이너스 하 나 를 더 하면 더 작 기 때문이다.이때 문제 가 배열 의 연속 을 요구 하기 때문에 원 sum 을 유지 할 수 없 기 때문에 sum 은 A [i] 에서 시작 한 새로운 단수 와 같 을 수 밖 에 없다. 이 숫자 는 새로운 candidate 를 형성 할 수 밖 에 없다.3. 새로운 candidate 를 얻 을 때마다 전체적인 result 와 비교 하면 최종 답 을 찾 을 수 있 습 니 다.순환 과정 에서 result 로 역사상 가장 큰 값 을 기록 합 니 다.A [0] 부터 A [n - 1] 까지 한 걸음 한 걸음 진행한다.

//    Kadane's algorithm
//        O(N)，           。
bool g_InvalidInput = false;//          1.         0    2.          

int maxSubArray(int *data, int n) {
	if(data == NULL || n <= 0) {
		g_InvalidInput = true;
		return 0;
	}
	
    int currSum = 0; //        currSumm = INT_MIN  OK。
    int result = 0x800000000; //       result = 0x800000000               。
    for(int i = 0; i < n; ++i){
        if(currSum >= 0)
            currSum += data[i];
		else
            currSum = data[i];
		
        if(currSum > result){
            result = currSum;
        }
    }
    return result;
}

이 문제 가 최대 sum 서브 배열 의 시작 표시 와 끝 표시 로 돌아 가 야 한다 면?조금 만 고치 면 돼.

vector maxSubArray(int *data, int n) {
    int sum = 0; //        summ = INT_MIN  OK。
    int result = INT_MIN; //       result=INT_MIN               。
	int start = 0;  
    int end = 0;
	vector res_index;  
    for(int i = 0; i < n; ++i){
        if(sum >= 0)
            sum += data[i];
		else {
			sum = data[i];
			start = i;	
		}
		
        if(sum > result){
            result = sum;
			end = i;
        }
    }
    res_index.push_back(start);  
    res_index.push_back(end);  
    return res_index;  
}

152. Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array  [2,3,-2,4] , the contiguous subarray  [2,3]  has the largest product =  6 .
최대 곱셈 서브 그룹.한 번 순환 하면 문 제 를 해결 할 수 있 습 니 다. 배열 에 양수 음수 가 나타 나 기 때문에 우 리 는 특정한 위치 에 있 을 때의 최대 치 와 최소 치 를 기록 해 야 합 니 다. 최소 치 는 다음 단계 에 음 수 를 곱 하면 최대 치가 될 수 있 기 때 문 입 니 다.

class Solution {
public:
    int maxProduct(vector& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        
        int currMax, currMin, result;
        currMax = currMin = result = nums[0];
        
        for(int i = 1; i < n; ++i) {
            int tmpMax = currMax * nums[i];
            int tmpMin = currMin * nums[i];
            //    tmpmax，   currMax *= nums[i],       ，          
            currMax = max(nums[i], max(tmpMax, tmpMin));
            currMin = min(nums[i], min(tmpMax, tmpMin));
            
            result = max(result, currMax);
        }
        return result;
    }
};

198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
사실은 주어진 배열 에서 하위 배열 을 찾 는 것 이다. 하위 배열 의 모든 요 소 는 서로 인접 하지 못 하고 그 최대 화 를 구 하 는 것 이다.
배달 관 계 는 dp [i] = max (dp [i - 2] + num [i], dp [i - 1]): 훔 치 려 면 이전 단 계 는 훔 치지 않 아야 합 니 다.만약 훔 치지 않 는 다 면, 지난번 에는 무엇이든 상관없다.

class Solution {
public:
    int rob(vector& nums) {
        int len = nums.size();
        if(len == 0)
            return 0;
        if(len == 1)
            return nums[0];
        
        vector dp(len, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < len; ++i) {
            dp[i] = max(dp[i - 1], dp[i- 2] + nums[i]);
        }
        return dp[len - 1];
    }
};

 
매번 교체 할 때마다 dp 와 인접 한 두 가지 옵션 만 터치 하기 때문에 공간 을 두 가지 요소 로 압축 하면 됩 니 다.하 나 는 take 이 고 하 나 는 dontTake 이 며 현재 의 최대 치 를 기록 합 니 다.

int rob(vector& nums) {
	int take = 0;
	int dontTake = 0;
	int maxProfit = 0; 
	
	for(int i = 0 ; i < nums.size(); ++i){
		take = nonTake + nums[i]; 
		dontTake = maxProfit; 
		maxProfit = max(take, dontTake);
	}
	return maxProfit;
}

213. House Robber II
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.최대 화 를 구하 다.
사고방식: 두 번 옮 겨 다 니 기: 한 번 은 nums [0] 를 포함 하지 않 고 한 번 은 nums [n - 1] 를 포함 하지 않 습 니 다.정 답 은 둘 의 최대 치 ~

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        
        int take = 0, dontTake = 0, profit1 = 0, profit2 = 0;
        for(int i = 0; i < n - 1; ++i) {
            take = dontTake + nums[i];
            dontTake = profit1;
            profit1 = max(take, dontTake);
        }
        take = 0, dontTake = 0;
        for(int i = 1; i < n; ++i) {
            take = dontTake + nums[i];
            dontTake = profit2;
            profit2 = max(take, dontTake);
        }
        return max(profit1, profit2);
    }
};