매일프로그래밍 - Question 1

매일프로그래밍 - Question 1

---

정수 배열(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

---

출처 : https://mailprogramming.com/

분석

---

음.. 사실 문제 자체를 이해를 못했다. 가장 큰 이어지는 원소들의 합...?? 무슨 말일까 저게...

난 한국인이 아닌가.. 그래서 친구를 소환해서 해석을 부탁했다. ( ´ ▽ ` )ﾉ

이어지는 원소들의 합이 가장 큰 부분. 

와. 친구야 너 내 전용 통역사 해주라. 이어지는 것들 중에 합이 가장 큰 걸 구하면 되는 부분?

-1

-1 + 3 = 2

-1 + 3 + -1 = 1

-1 + 3 + -1 + 5 = 6

3 + -1 = 2

3 + -1 + 5 = 7

-1 + 5 = 6

5

첫 번째 배열부터 하나씩 차례로 더하는데, 더한 값(sumResult)이 현재 가장 큰 값(maxResult) 보다 작으면 버려지고, 더한 값(sumResult)이 현재 가장 큰 값(maxResult) 보다 크면 더한 값(sumResult)이 현재 가장 큰 값(maxResult)가 된다.

sumResult < maxResult ::: maxResult = maxResult

sumResult > maxResult ::: maxResult = sumResult

소스 및 풀이

---

public static void main(String[] args) {
		int maxResult; //현재 가장 큰 값
		int sumResult; //더한 값
		int[] num = {2, 4, -2, -3, 8}; //주어진 정수배열
		maxResult = num[0];
		for(int i=0; i<num.length; i++) {
			sumResult = num[i];
			if(num[i]>maxResult) {
				maxResult = num[i];
			}
			for(int j=i+1; j<num.length; j++) {
				sumResult += num[j];
				if(sumResult>maxResult) {
					maxResult = sumResult;
				}
			}
		}
		System.out.println("Result : " +maxResult);
	}

2~4행 : 선언 부분

6행, 11행 : for문 2개 사용

7행 : 기준이 되는 배열로 sumResult 초기화

8행 : 기준이 되는 배열이 maxResult 보다 크면, 기준이 되는 배열값이 maxResult가 된다.

12행, 13행 : 새로운 sumResult과 maxResult와 비교.

18행 : 결과 출력

결과

---

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

매일프로그래밍 풀이

---

풀이보고 충격먹었다. 나 너무 하드코딩이야아아.. java math 클래스를 이용하면 더 편하다는 것.

역시 아는 만큼 보인다... 머리가 나쁘면 몸이 고생한다... (*`н´*)

수정한 소스

---

public static void main(String[] args) {
		int maxResult;
		int sumResult = 0;
		int[] num = {2, 4, -2, -3, 8};
		maxResult = num[0];
		for(int i=0; i<num.length; i++) {
			sumResult = Math.max(sumResult+num[i], num[i]);
			maxResult = Math.max(sumResult, maxResult);
		}
		System.out.println("Result : " +maxResult);
	}

**** Java math 클래스 이용.

7행 : 더해진 새로운 값(sumResult+num[i])와 현재 배열 값을 비교해서 큰 것이 sumResult.

8행 : sumResult와 maxResult를 비교.

... 허탈하다