문제풀이 - 정렬된 두 배열 합치기, 연속된 부분 배열의 가장 큰 합 구하기

정렬된 두 배열을 받아서, 전체 배열에서 k번째 요소를 리턴하는 문제

 

public int getItemFromTwoSortedArrays(int[] arr1, int[] arr2, int k){
    int arr1_idx=0;
    int arr2_idx=0;

    int arr1_len= arr1.length;
    int arr2_len = arr2.length;

    int[] answer = new int[arr1_len + arr2_len];
    int answer_idx=0;

    while(arr1_idx < arr1_len && arr2_idx < arr2_len){
        if(arr1[arr1_idx] <arr2[arr2_idx])
            answer[answer_idx++] = arr1[arr1_idx++];
        else
            answer[answer_idx++] = arr2[arr2_idx++];
    }

    while (arr1_idx < arr1_len) {
        answer[answer_idx++] = arr1[arr1_idx++];
    }

    while(arr2_idx < arr2_len) {
        answer[answer_idx++] = arr2[arr2_idx++];
    }

    return answer[k];
}

 

 

 

연속된 부분 배열의 가장 큰 합을 구하기

 public int LSCS(int[] arr){
    int subArrSum = 0;
    int max = Integer.MIN_VALUE;
    
    for(int i=0;i<arr.length;i++){
        subArrSum = subArrSum + arr[i];
        if (subArrSum > max){ max = subArrSum;}
        
        if(subArrSum<0)//합이 음수인 경우, 초기화
            subArrSum = 0;
    }
    return max;
}