스냅 53 최대 자동 정렬 및
1735 단어 버클-dp
nums
을 정하고, 최대 화합을 가진 연속 서브 그룹 (서브 그룹은 최소한 원소를 포함) 을 찾아 최대 화합을 되돌려줍니다.예:
: [-2,1,-3,4,-1,2,1,-5,4],
: 6
: [4,-1,2,1] , 6。
동적 기획 방정식: dp[i]=max(dp[i-1]+nums[i],nums[i])
사고방식 1: O(n)
class Solution {
public int maxSubArray(int[] nums) {
int sum=0;
int res=nums[0];
for(int i=0;i0)
sum+=nums[i];
else
sum=nums[i];
res=Math.max(res,sum);
}
return res;
}
}
사고방식2: 분치법
왼쪽 부분에서 뒤에서 앞으로 찾기 (mid---0)
오른쪽 부분에서 이동해서 찾기 (mid+1--length),
class Solution {
public int maxSubArray(int[] nums) {
return maxSubArrayPart(nums,0,nums.length-1);
}
private int maxSubArrayPart(int[] nums,int left,int right){
if(left==right){
return nums[left];
}
int mid=(left+right)/2;
return Math.max(
maxSubArrayPart(nums,left,mid),
Math.max(
maxSubArrayPart(nums,mid+1,right),
maxSubArrayAll(nums,left,mid,right)
)
);
}
private int maxSubArrayAll(int[] nums,int left,int mid,int right){
int leftSum=0;
int sum=0;
for(int i=mid;i>=left;i--){
sum+=nums[i];
if(sum>leftSum){
leftSum=sum;
}
}
sum=0;
int rightSum=Integer.MIN_VALUE;
for(int i=mid+1;i<=right;i++){
sum+=nums[i];
if(sum>rightSum){
rightSum=sum;
}
}
return leftSum+rightSum;
}
}