APCS202206 第4題內積

作業上傳：http://203.68.236.9/problem/c0303

zerojudge  https://zerojudge.tw/ShowProblem?problemid=i402

出處：APCS

輸出說明

輸出一個整數代表內積最大值。

輸入範例

5 5

-3 -3 3 3 -3

2 2 2 2 2

5 5

-3 -3 -3 5 -5

-5 5 -3 -3 -3

4 3

1 2 3 4

-1 -2 -3

輸出範例

12

77

-1

解題策略

枚舉、模擬、貪婪

枚舉兩陣列的內積的所有可能性

Step1)先取A陣列的最後一個，與B陣列的第一個求內積，更新最大值。

Step2)取A陣列的最後兩個，與B陣列的前面兩個求內積，首先計算A陣列倒數第二個與B陣列第一個內積到加總值(sum)，更新最大值，如果加總值(sum)小於0則更新為0，接著累加A陣列倒數第一個與B陣列第二個內積到加總值(sum)，更新最大值，此時已經計算出兩個區段的內積，減少重覆計算，有DP的精神。如果前一個相鄰點的內積大於0，則累加起來一定會更大，如果相鄰點的內積小於0，則歸0才能求出更大內積。

Step3)取A陣列的最後三個，與B陣列的前面三個求內積，首先計算A陣列倒數第三個與B陣列第一個內積到加總值(sum)，更新最大值，如果加總值(sum)小於0則更新為0，接著累加A陣列倒數第二個與B陣列第二個內積到加總值(sum)，更新最大值，此時已經計算出兩個區段的內積，減少重覆計算，有DP的精神，接著累加A陣列倒數第一個與B陣列第三個內積到加總值(sum)，更新最大值，此時已經計算出三個區段的內積，減少重覆計算，有DP的精神。如果前一個相鄰點的內積大於0，則累加起來一定會更大，如果相鄰點的內積小於0，則歸0才能求出更大內積。

依此類推，直到陣列A第一個元素與陣列B最後一個元素求內積。

Step4)反向也需要計算一次。