Tìm thuật toán tối ưu cho bài toán tìm 2 phần tử có tích lớn nhất trong mảng bất kỳ

[Code_for_food]

Bài toán: tìm 2 phần tử có tích lớn nhất trong mảng bất kỳ

// mảng (input) đề bài ⇛ đáp án: 5 và 7
const arr = [- 3, 3, 2, 4, 5, 7, 2, 3, 3];


// để chứa kết quả tích một phần tủ với phần tử liền kề bên phải: 
let table = {}; 
┌─────────┬────────┐
│ (index) │ Values │
├─────────┼────────┤
│    6    │   6    │
│    8    │   2    │
│    9    │   7    │
│   14    │   5    │
│   20    │   3    │
│   35    │   4    │
│   -9    │   0    │
└─────────┴────────┘
// duyệt đề bài
for (let i = 0; i <= arr.length; i++) {

  //if này để không tính tích phần tử cuối cùng với phần tử phía sau (vượt array.lenght)
  if (i + 2 <= arr.length) {

    // insert record vào bảng dò
    table[arr[i] * arr[i + 1]] = i;
  }
}

//lại quay về bài toán tìm phần tử lớn nhất trong mảng, mảng này là cột index bên trên [6, 8, 9, 14, 20, 35, -9]
const indexInArr = table[Math.max(...Object.keys(table))];

// dòng này ai cũng biết
console.log(arr[indexInArr], ' và ', arr[indexInArr + 1]);

Không biết em bị rơi vào trường hợp code trâu không?

Code trâu là gì?

mọi người cho em hỏi code trâu là gì vậy ạ… thấy các bạn bảo code trâu là hạ sách khi đi thi… em cảm ơn mọi người lấy ví dụ về code trâu giúp em thì càng tốt ạ cảm ơn ạ

[noname00 (HK boy)]

Code của bạn là code trâu rồi.

Gợi ý: Bài này cần sort mảng trước rồi xét vài trường hợp (liên quan đến số âm, số dương và số 0).

[Code_for_food]

Vâng anh, đúng là code trâu thật rồi :))) Bài này chỉ cần sort tăng dần rồi lấy 2 phần tử cuối là xong :)))

[noname00 (HK boy)]

Nếu mảng a = [-5, -4, 0, 3, 4] thì đâu thể lấy 2 phần tử cuối được hả bạn.

[Code_for_food]

Vậy thì em tính 3 trường hợp sau khi sort a

• tích 2 phần tử cuối là 3 và 4
• tích 2 phẩn tử đầu là -5 và -4
• tích 1 phần tử đầu và 1 phần tử cuối là -5 và 4

Rồi chọn sort tiếp 3 kết quả này, xong lấy giá trị cuối cùng là -5 và -4

Nhưng nó vẫn ngoằn ngoèo như cách bên trên

[noname00 (HK boy)]

Xét 3 trường hợp O(1) thì có gì mà phức tạp hả bạn Bạn đang nghĩ phức tạp quá đó.

[Code_for_food]

-5 * -4 ra 20 rồi mang số 20 này đi so sánh, xong từ số 20 này phải suy ngược ra 2 index, từ 2 index này mới tìm ra -5 với -4 nữa anh.

[noname00 (HK boy)]

Bạn tạo 1 mảng tên enumerate chứa [phần tử, index], rồi sort và xử lý trên mảng enumerate này là được.

[Code_for_food]

enumerate như này à anh

const foobar = ['A', 'B', 'C'];

for (const [index, element] of foobar.entries()) {
  console.log(index, element);
}

[noname00 (HK boy)]

Theo ý tưởng của mình thì enumerate như thế này:

let enumerate = arr.map((ele, idx) => [ele, idx]);
// sắp xếp enumerate theo thứ tự các phần tử (trong mảng arr) tăng dần,
// nếu 2 phần tử nào bằng nhau thì phần tử có index nhỏ hơn sẽ đứng trước
enumerate.sort((t1, t2) => t1[0] - t2[0] < 0 || (t1[0] == t2[0] && t1[1] - t2[1] < 0));

[rogp10]

Đầu tiên xét trường hợp đặc biệt là mảng có đúng 2 phần tử. Với bài này ta tìm 2 số không âm max và 2 số âm min trên cùng 1 mảng, vì với mảng có 3 phần tử trở lên phải có ít nhất một cặp số như vậy.