兩個子陣列元素之間的最大絕對差異

Question

給定一個數組。整數K將數組分成兩個子數組。 diffK定義爲max({A[0], A[1],....A[K]})- max({A[K+1],A[K+2],...A[n-1]})。返回最大絕對值diifK。時間複雜性必須是O(n)和最大空間complexity O(n)

Answer 1

在通過數組的單向傳遞中構建跟蹤通過給定索引看到的最大值的「助手」數組很容易。 （因此，對於任何給定的K，helper[K] = max({A[0], A[1],....A[K]})。）

然後，在單次通過向後通過陣列，可以跟蹤從向前一個給定的索引（max({A[K+1],A[K+2],...A[n-1]})，其中K是索引）觀察的最大值，並將其與該索引處的上述「助手」數組的值進行比較。跟蹤您在同一索引處的兩個值之間所看到的最大差異，並返回結果。