๐ฑ๐ป3๏ธโฃ, ์ฐ์ ํ์ค ๋ถ๋ถ ์์ด์ ํฉ[161988]
๐ง ํ๋ก์ธ์ค
๋ฌธ์ ์ค๋ช
์ด๋ค ์์ด์ ์ฐ์ ๋ถ๋ถ ์์ด์ ๊ฐ์ ๊ธธ์ด์ ํ์ค ์์ด์ ๊ฐ ์์๋ผ๋ฆฌ ๊ณฑํ์ฌ ์ฐ์ ํ์ค ๋ถ๋ถ ์์ด์ ๋ง๋ค๋ ค ํฉ๋๋ค. ํ์ค ์์ด์ด๋ [1, -1, 1, -1 …] ๋๋ [-1, 1, -1, 1 …] ๊ณผ ๊ฐ์ด 1 ๋๋ -1๋ก ์์ํ๋ฉด์ 1๊ณผ -1์ด ๋ฒ๊ฐ์ ๋์ค๋ ์์ด์
๋๋ค.
์๋ฅผ ๋ค์ด ์์ด [2, 3, -6, 1, 3, -1, 2, 4]์ ์ฐ์ ๋ถ๋ถ ์์ด [3, -6, 1]์ ํ์ค ์์ด [1, -1, 1]์ ๊ณฑํ๋ฉด ์ฐ์ ํ์ค ๋ถ๋ถ์์ด์ [3, 6, 1]์ด ๋ฉ๋๋ค. ๋ ๋ค๋ฅธ ์์๋ก ์ฐ์ ๋ถ๋ถ ์์ด [3, -1, 2, 4]์ ํ์ค ์์ด [-1, 1, -1, 1]์ ๊ณฑํ๋ฉด ์ฐ์ ํ์ค ๋ถ๋ถ์์ด์ [-3, -1, -2, 4]์ด ๋ฉ๋๋ค.
์ ์ ์์ด sequence๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ฐ์ ํ์ค ๋ถ๋ถ ์์ด์ ํฉ ์ค ๊ฐ์ฅ ํฐ ๊ฒ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๐ฝ ๋ฌธ์ ํ์ด
sequence ์ ๊ธธ์ด๊ฐ 500,000 ๊น์ง ๊ฐ๋ฅํ๋ค๋ ์ ์ฝ ์กฐ๊ฑด์ด ์์ด์ ๋ฌด์ง์ฑ์ผ๋ก ๋ฐ๋ณต๋ฌธ์ ๋๋ฆฌ๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ ๊ฒ์ด๋ค. ๋ํ ํ์ค ์์ด์ ๊ณฑํด์ผ ํ๋๊น 1๋ถํฐ ์์ํ๋ ๊ฒฝ์ฐ์ -1๋ถํฐ ์์ํ๋ ๊ฒฝ์ฐ ๋๊ฐ์ง๋ฅผ ๋ชจ๋ ๊ณ ๋ คํด์ผ ํ๋ค.
๊ทธ๋ ๊ธฐ์ ์๊ฐํ ๊ณ ์์ ์ ์ฒด ๋ฐฐ์ด์ 1๋ถํฐ ๊ณฑํ ๋ฐฐ์ด ํ๊ฐ์ -1๋ถํฐ ๊ณฑํฉ ๋ฐฐ์ด ํ๊ฐ์ ๋ํ ์ต๋ ์ฐ์ ๋ถ๋ถ ์์ด์ ํฉ์ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ๊ณ ์ํ๋ค. ํ๋ํ๋ ์ดํด๋ณด์.
public static long maxSum(int[] arr) {
long max = 0L;
long[] dp = new long[arr.length];
dp[0] = arr[0];
max = arr[0];
for(int i=1; i<dp.length; i++) {
// ์ด์ ๊น์ง์ ์ต๋๊ฐ + ํ์ฌ๊ฐ ๊ณผ ํ์ฌ๊ฐ์ ๋น๊ต
dp[i] = Math.max(dp[i-1] + arr1[i], arr1[i]);
max = Math.max(dp[i], max);
}
return max;
}
์ฐ์ ๋ถ๋ถ ์์ด์ ์ต๋ ํฉ์ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๋ค. ์ด์ ๊น์ง์ ์ต๋๊ฐ + ํ์ฌ ๊ฐ, ํ์ฌ ๊ฐ์ ๋น๊ตํ์ฌ dp ์ ์ ์ฅํ๊ณ max ์ ๊ฐ์ ๊ฐฑ์ ํ๋ค. ์ด๋ฌํ ๋ฐฉ์์ผ๋ก ์ต๋ ํฉ์ ๋์ถํ๋ค.
public long solution(int[] sequence) {
int[] seq1 = new int[sequence.length];
int[] seq2 = new int[sequence.length];
for(int i=0; i<sequence.length; i++) {
if(i%2==0) {
seq1[i] = sequence[i];
seq2[i] = sequence[i] * -1;
} else {
seq1[i] = sequence[i] * -1;
seq2[i] = sequence[i];
}
}
return maxSum(seq1, seq2);
}
์์ ๊ฐ์ ๋ฐฉ๋ฒ์ ํตํด seq1 ์ 1๋ถํฐ, seq2 ๋ -1๋ถํฐ ๊ณฑํ ํ์ค ์์ด์ ๊ตฌํํ ํ, maxSum ์ ํตํด ํ๋ฒ์ ๋ต์ ๋์ถํ๋ค.
โ
์ ์ฒด์ฝ๋
import java.util.*;
import java.util.stream.*;
public class Solution {
public static void main(String[] args) {
int[] sequence = {2,3,-6,1,3,-1,2,4};
long answer = solution(sequence);
System.out.println(answer);
}
static long solution(int[] sequence) {
int[] seq1 = new int[sequence.length];
int[] seq2 = new int[sequence.length];
for(int i=0; i<sequence.length; i++) {
if(i%2==0) {
seq1[i] = sequence[i];
seq2[i] = sequence[i] * -1;
} else {
seq1[i] = sequence[i] * -1;
seq2[i] = sequence[i];
}
}
return maxSum(seq1, seq2);
}
public static long maxSum(int[] arr1, int[] arr2) {
long max = 0L;
long[] dp1 = new long[arr1.length];
long[] dp2 = new long[arr1.length];
dp1[0] = arr1[0];
dp2[0] = arr2[0];
max = Math.max(arr1[0], arr2[0]);
for(int i=1; i<dp1.length; i++) {
// ์ด์ ๊น์ง์ ์ต๋๊ฐ + ํ์ฌ๊ฐ ๊ณผ ํ์ฌ๊ฐ์ ๋น๊ต
dp1[i] = Math.max(dp1[i-1] + arr1[i], arr1[i]);
dp2[i] = Math.max(dp2[i-1] + arr2[i], arr2[i]);
max = Math.max(max, Math.max(dp1[i], dp2[i]));
}
return max;
}
}
์์์ ๊ฐ์ด 100,000๊น์ง ๊ฐ๋ฅํ๋ค. ์ต๋์ ๊ฒฝ์ฐ 100,000 X 500,000 = 50,000,000,000 ๋ก int ์ ์ต๋ ๋ฒ์๋ฅผ ๋์ ์ ์์ผ๋ฏ๋ก long ์ ์ฌ์ฉํจ์ ์ฃผ์ํ์