Hey guys, Can anyone give an approach or link their soln for 2nd problem of icpc kolkata online round ‘Finding Hardest Sum Value’ ?
Perform maximum sum subarray DP for each of the N*M points in all 4 directions. It can be done in O(4 * N * M) time. Now, iterate through each point in matrix, fixing it as meeting point of all 4 persons. Each point’s optimal value can be found in O(1) time, using the already computed values. Find the best point and report its value
Thanks…
Still new gotta learn more dp algos
Btw that O(4 * N * M) time for computing subarrays for all n*m points??
Each direction max subarray dp will take O(N) time too right??
So should,nt it be O(4 * N * N * M )