Show problems as
Classic problem #3287HardArrayDynamic ProgrammingBit Manipulation

Find the Maximum Sequence Value of Array

Real-world version: Two Trays of Punch Cards
Tracked in this browser only
Read Find the Maximum Sequence Value of Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rack holds punch cards in a row, codes[i] being the code punched on the i-th card. Every code is below 128.

Take exactly 2 * pick cards off the rack, keeping the rack's order. The first pick cards you took go on the left tray and the last pick on the right tray.

The reading of such a choice is the bitwise OR of the left tray's codes, XOR the bitwise OR of the right tray's codes. Return the largest reading you can get.

Examples

Example 1

Input
codes = [1, 2, 4, 8], pick = 2
Output
15

All four cards are taken, so the left tray ORs to 3 and the right tray to 12. Those share no bits, so the reading is 15.

Example 2

Input
codes = [127, 1, 1, 127], pick = 1
Output
126

Putting a card punched 127 on one tray and a card punched 1 on the other leaves every bit set but the lowest, which is 126. No choice does better, since both trays would have to differ in all seven bits.

Example 3

Input
codes = [8, 1, 1, 4, 2], pick = 2
Output
15

Skipping the third card puts 8 and 1 on the left tray for 9 and 4 and 2 on the right for 6, and 9 XOR 6 is 15. Taking four cards side by side never reaches that.

Constraints

  • 2 <= codes.length <= 400
  • 1 <= codes[i] <= 127
  • 1 <= pick <= 200
  • 2 * pick <= codes.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_value(codes: list[int], pick: int) -> int:
Java
public int maxValue(int[] codes, int pick)

More on the same topics