[Daily] 2021-06-14 MON

LeetCode

Plan

• Previous
  • Tree (this is mainly for DFS)
  • Array
  • String (this part was a bit of a drawback in last season’s tests.)
• To-Do
  • File I/O !!! (Mac Setting & basic things are broken… MUST!)
  • Database
  • String
  • Dynamic Programming

Today: Dynamic Programming

1043. Partition Array for Maximum Sum

k-size sliding windows within dp[i]

dp[i] = max(dp[i-j] + max(arr[i-1...i-j]) * j) ・・・・・・・・ j: [1, k]

iMax = arr[i];
for(int j=1; j<=k; j++) {
  iMax = max(iMax, arr[i-j]);
  dp[i] = max(dp[i], dp[i-j] + iMax*j);
}

Additional picks

• accumulate function:

  #include <numeric>
  accumulate(arr.begin(), arr.being()+k, 0);
  

• greater:

  sort(arr.begin(), arr.end(), greater<int>());