[매일프로그래밍] 4월 2일

매주 월요일에 코딩 문제를 보내주는 '매일 프로그래밍' 포스팅입니다. 해당 포스팅에 작성된 풀이 과정은 최선이 아닌 복기를 위한 회고록 목적으로 작성되었습니다. '매일 프로그래밍' 구독하기

4월 둘째주 포스팅 보기

4월 셋째주 포스팅 보기

4월 첫째주 월요일 

문제

---

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).

예제

Input: [-1, 3, -1, 5]

Output: 7 // 3 + (-1) + 5

Input: [-5, -3, -1]

Output: -1 // -1

Input: [2, 4, -2, -3, 8]

Output: 9 // 2 + 4 + (-2) + (-3) + 8

필자의 풀이

---

사용한 변수는 총 3개

• 현재 인덱스의 값인 변수 number

• 가장 큰 합을 도출한 변수 result

• 음수들의 합을 계산할 변수 minus

결과값이 0일 경우

• 인덱스의 값을 결과 값에 저장한다.

결과값이 0이 아닐 경우 

• 배열의 값이 음수일 경우

• 결과값이 음수인 경우 

• 결과값과 비교해 더 큰값을 저장한다.

• 결과값이 양수인 경우 

• 음수들의 합에 인덱스 값을 더한다.

• 배열의 값이 양수일 경우

• 음수들의 합이 0이 아닌 경우 

• 음수들의 합과 결과 값을 더했을때 음수인 경우 현재 값부터 다시 결과 값을 구한다.

• 음수들의 합과 결과 값을 더했을때 양수인 경우 결과값과 음수들의 합을 더한 값에 양수를 더한다.

• 음수들의 합이 0인 경우

• 결과 값이 0보다 작은 경우

• 결과 값에 현재 값을 저장한다.

• 결과 값이 0보다 큰 경우

• 결과값에 현재 값을 더한 값을 저장한다.

private void sumaryArray(int[] list, int index){

    int result=0;
    int number;
    int minus=0;

    for(int i=0;i<list.length;i++){
        number=list[i];

        if(result==0){
            result=number;
        }else{
            if(number<0){
                if(result<0){
                    if(result<number){
                        result=number;
                    }
                }else{
                    minus+=number;
                }
            }else{
                if(minus!=0){
                    if((minus+result)>0){
                        result=result+minus+number;
                    }else{
                        result=number;
                    }
                    minus=0;
                }else{
                    if(result<0){
                        result=number;
                    }else{
                        result+=number;
                    }
                }
            }
        }

    }

    WLog.e("TEST",index+"번 배열의 이어지는 가장 큰 값은 "+result+"입니다.");
}

 

결과 화면

---

제공된 풀이

---

풀이를 보고 너무 고민한 제가 부끄러웠습니다...

더 열심히 해야겠네요 

해당 포스팅은 '매일프로그래밍'에서 출제된 문제와 풀이를 참고했습니다.  문제시 삭제하도록 하겠습니다.