MAXSUM 질문이요 dmatrix MAXSUM 위의 문제가 연속적으로 입력받은 숫자에서 최대 연속적인 부분합을 찾는 문제인데 제가 작성한 답안에서 오류가 뭔지 모르겠습니다. 알고리즘은 다음과 같습니다. 음수 또는 0 사이의 양수값을 모두 더합니다. 기존의 부분합보다 이 값이 크면 최대값을 변경합니다. 문제에서 1 <= i <= j <= N 이므로 한자리의 합이 크면 이 값이 최대부분합이 되는거라 한자리만 계산될지라도 부분합을 최대로 하였습니다. #include <iostream> using namespace std; int GetMaxSum(int* const array, int size) { int maxSum = 0; int index = 0; while (index != size) { int sum = 0; for (int i = index; i != size; index = ++i) { if (array[i] <= 0) { ++index; break; } else { sum += array[i]; } } if (maxSum < sum) { maxSum = sum; } sum = 0; } return maxSum; } int main(int argc, char* argv[]) { int numOfCase = 0; cin >> numOfCase; for (int i = 0; i != numOfCase; ++i) { int size = 0; cin >> size; int* array = new int[size]; for (int j = 0; j != size; ++j) { cin >> array[j]; } cout << GetMaxSum(array, size) << endl; delete array; } return 0; } 9년 전
4개의 댓글이 있습니다. Signin 최대 합이 꼭 양수만으로 이루어지지는 않을 것 같습니다. 9년 전 link dmatrix 최대합이 양수가 아니면 0을 출력합니다. 왜냐하면 문제에 부분합의 범위를 아무것도 선택하지 않으면 0이다 라는 조건이 있습니다. 9년 전 link Signin 음.. 그런 뜻으로 드린 말씀은 아니었는데 제가 잘 못 말씀드린 것 같습니다. 2 -1 2 2 2 의 경우 dmatrix님의 코드는 6을 답으로 출력하지만, 실제 답은 모든 구간을 포함하는 7이 되어야 합니다. 이러한 케이스도 포함하도록 알고리즘을 바꾸시면 될 것 같습니다 :) 9년 전 link dmatrix 아 감사합니다!! :) 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
dmatrix
MAXSUM
위의 문제가 연속적으로 입력받은 숫자에서 최대 연속적인 부분합을
찾는 문제인데 제가 작성한 답안에서 오류가 뭔지 모르겠습니다.
알고리즘은 다음과 같습니다.
문제에서 1 <= i <= j <= N 이므로 한자리의 합이 크면
이 값이 최대부분합이 되는거라 한자리만 계산될지라도
부분합을 최대로 하였습니다.
9년 전