아까 물어보신게 2차원 배열 에서 maximum subarray인거 같은데
일단 1차원 배열 중엔
https://en.wikipedia.org/wiki/Maximum_subarray_problem
를 읽어보시면 [3,-4,5,19,-55,34,65,6] 이런 배열에서 어디부터 더해야 최대 값인지 알아내는 문제가 있거든요 저 링크에서 Kadane's algorithm 읽어보시면 대충 내용이
0번째 배열부터 now=now+a[i]로 계속 더해주고 max 라는 걸 하나 만들어둔다음에 (맨처음엔 둘다 0으로 초기화)
now와 max를 비교해서 now가 max보다 크면 max에 now를 대입하고 아니라면 now를 다시 0으로 초기화 하면서 반복문 진행하면 1차원 배열에서 subarray의 최대값이 나옴 (이유는 그냥 상식적으로 생각해보면 subarray 라는게 이어져 있어야 하는데 0부터 i까지 더한 subarray 값이 내가 예전에 구했던 max보다 작다면 더이상 기억할 필요가 없음)
이런식으로 1차원 배열 subarray의 최대값을 구하는게 kadane's algorithm 인데 이걸 2차원 배열에 적용하면 ㅇㅇㅋ
2차원 배열로 확장시키는 방법은
https://youtu.be/yCQN096CwWM
이거 보시면 이해될듯함 (주어진 문제에선 어느 subarray인지 index를 구할필요는 없었으니 maxleft,right,up,down은 필요없을듯)
정보 | 2719명이 읽었어요. 18.116.63.174
