정수배열이 있고
배열 인덱스 i에 대해서
i를 포함하는 부분배열의 합
혹은
i를 포함하는 부분배열 중 원소 하나 제외한 것(i는 포함해야함)의 합
의 최댓값을 모든 i에 대해 구하는 문제인데
배열 크기가 최대 20만에 시간제한 1초라서
세그트리나 투포인터인가 싶어서 고민해봤는데
하나 빼도 되는 조건 때문에 잘 모르겠네
혹시 어떻게 풀면될까
배열 인덱스 i에 대해서
i를 포함하는 부분배열의 합
혹은
i를 포함하는 부분배열 중 원소 하나 제외한 것(i는 포함해야함)의 합
의 최댓값을 모든 i에 대해 구하는 문제인데
배열 크기가 최대 20만에 시간제한 1초라서
세그트리나 투포인터인가 싶어서 고민해봤는데
하나 빼도 되는 조건 때문에 잘 모르겠네
혹시 어떻게 풀면될까
A를 수열, S를 누적합이라 하면 어떤 i에 대해 S[y] - S[x] - min(A[z],0)의 최댓값을 묻는 문제. x< i != z <=y 일단 min 없다 생각하면 각 i에 대해 max(S[y]) - min(S[x]) 하면 최대임. 저걸 구하는 방식을 응용하면 i:0->n-1 iteration에서 S[x]의 최솟값을 구할 때 S[x] + A[z]의 최솟값도 같이 구해주고 i: n-1->0 iteration에서 S[y]의 최댓값을 구할 때 S[y] - A[z]의 최댓값을 함께 구해주면서 적당히 교차하게 최댓값 구해주면 됨.
S를 n-1 순회하면서 최댓값 메모, 0부터 순회하면서 최솟값 메모는 알겠는데 여기서 (S + Az도 메모하기위해) min을 갱신해가면서 빼주면 구간 밖의 원소를 빼는거 같은데.. 내가 잘못이해한건가??
0~n-1 순회할 때 S[0]~S[i-1]들의 최솟값을 저장하면 S[x] - A[i]가 지금까지 S[x] - A[z]의 후보가 되겠지. 이걸 더 작은 i에 대해서도 해줄거고 그러면 i에서는 S[x] - A[z: 0~i-1] 들의 최솟값을 들고 있게 되고 이게 가장 작은거임. 반대쪽도 마찬가지. 항상 i보다 작은 j에 대해 -A[j] 해줬기 때문에 구간 안에는 항상 속함.
발상은 좋으나 틀린풀이임
반례 ㄱㄴ?
그냥 금광세그에 노드에 한개 제외한것 추가하면 될거같은데
왼쪽오른쪽 최댓값 합, 왼쪽하나뺀거+오른쪽 최댓값 합, 오른쪽하나뺀거+왼쪽 최댓값 합
a=2*i,b=2*i+1 seg[i].left_one= max(seg[b].left_one+seg[a].sum, seg[a].left_one, seg[lo].left_max-arr[left_index]) 대충 이런식으로 업데이트하면될거같아요