Tối đa subarray brute force javascript

Đây là giải pháp rõ ràng nhất, nhưng không may là không hiệu quả lắm. Tôi sẽ không dành quá nhiều thời gian ở đây, nhưng ý tưởng cơ bản là bạn tính tổng của mọi mảng con liền kề có thể và play-king-of-the-hill với một biến maxSum. Tôi sẽ chia nhỏ nó hơn nữa bên dưới

Trực giác

→ Quét qua từng ô trong mảng.
→ Khởi tạo maxSum và đặt thành -Infinity.

→→ Đặt currSum thành 0.
→→ Quét qua bắt đầu từ chỉ mục hiện tại cho đến hết mảng.

→→→ Thêm từng chỉ mục vào currSum.
→→→ kiểm tra xem nó có lớn hơn maxSum không. Nếu vậy thì gán currSum cho maxSum.

→ Trả về maxSum

Mã số

function findMaxSubArrayBruteForce(arr) { 
  let maxSum = -Infinity;
  let currSum;  
  for (var i = 0; i < len; i++) {  
    currSum = 0;   
    for (var j = i; j < len; j++) {   
      currSum += arr[j];    
      if (maxSum < currSum) {   
        maxSum = currSum;      
      }   
    } 
  } 
  return maxSum;
}

Phân tích O lớn

Thời gian. O(n²)
Vòng lặp for lồng nhau thực hiện phép toán n².
Không gian. O(1)
Bộ nhớ được phân bổ không tăng dựa trên đầu vào.

Giải pháp tuyến tính

Chìa khóa của giải pháp này là hiểu được vai trò của các số âm

Input: [-2,-11,-13,-2,-14,-9,-5,-15,-3],
Output: -2
Explanation: [-2] has the largest sum = -2.

Trong ví dụ trên, tất cả các số đều là số âm. Điều này có nghĩa là cộng hai cái lại với nhau sẽ luôn tệ hơn là chỉ dùng cái thấp hơn. Tuy nhiên, các số âm có thể hữu ích để tính tổng

Input: [2,1,-1,4],
Output: 6
Explanation: [2,1,-1,4] has the largest sum = 6.

Trong ví dụ trên, số âm được sử dụng làm cầu nối giữa các số dương ở một bên và số dương ở bên kia. Nếu chúng ta thay đổi ví dụ này một chút, chúng ta có thể thấy cây cầu không hữu ích ở điểm nào

Input: [2,1,-3,4],
Output: 4
Explanation: [2,1,-3,4] has the largest sum = 4.

Tổng của ba ký tự đầu tiên bằng không. Điều này có nghĩa là tổng của mảng liền kề về cơ bản bắt đầu lại. Trên thực tế, mảng liền kề có thể bắt đầu lại từ số 4 (chỉ số thứ ba này) và điều đó thậm chí không thành vấn đề

Thử thách này là một trong những minh họa yêu thích của tôi về giá trị của việc sử dụng đúng công cụ để giải quyết vấn đề. Là nhà phát triển web, chúng ta thường sử dụng nhiều mẫu thiết kế giống nhau để giải quyết vấn đề lặp đi lặp lại. Điều đó thật tuyệt. Việc học các mẫu hiệu quả cho phép chúng ta giải quyết nhiều vấn đề gặp phải nhanh chóng và hiệu quả hơn. Có một lý do tại sao bản năng giải quyết vấn đề lại tuân theo một số thói quen đã định sẵn, thường tập trung vào các vòng lặp lặp đi lặp lại

Tuy nhiên, sự quen thuộc này có thể đóng băng chúng ta trong vùng thoải mái của mình, dẫn đến suy nghĩ cứng nhắc và cản trở chúng ta khám phá các giải pháp sáng tạo hơn có thể hiệu quả hơn, dễ dàng hơn hoặc đơn giản là cần thiết để giải quyết các vấn đề bất thường hoặc phức tạp

“Tôi cho rằng thật hấp dẫn, nếu công cụ duy nhất bạn có là một cái búa, để coi mọi thứ như thể nó là một cái đinh”

Chúng ta có thói quen coi các vòng lặp là công cụ cần thiết cho mọi thứ. Cần thêm một nhiệm vụ nữa? . Chúng tôi nhận được kết quả chúng tôi cần. Chung ta se đi tiêp. Nhiều thời gian?

Tuy nhiên, chúng ta chắc chắn sẽ gặp phải những tình huống không ổn. Mảng lớn. Dữ liệu phức tạp. Áp dụng “cái búa” của chúng tôi (i. e. các vòng lặp lồng nhau và các phương pháp giải quyết vấn đề tương tự) đối với những thách thức này có thể đòi hỏi rất nhiều thời gian và sức mạnh tính toán. Về mặt kỹ thuật, các giải pháp vũ phu này có thể có khả năng trả lại kết quả mong muốn của chúng tôi. Tuy nhiên, thời gian và sức mạnh tính toán cần thiết có thể khiến chúng trở nên vô dụng về cơ bản, với một tập dữ liệu đủ lớn hoặc phức tạp.

Các vấn đề chỉ có thể được giải quyết một cách hiệu quả và hiệu quả bằng các thuật toán giúp loại bỏ chúng ta khỏi thói quen của mình, dạy chúng ta suy nghĩ về chi phí thời gian và không gian của các loại giải pháp khác nhau và thêm các công cụ khác ngoài những chiếc búa đáng tin cậy vào vấn đề lập trình của chúng ta-

Ok, đủ về búa. Còn việc tìm tổng mảng con lớn nhất của một mảng thì sao?

Chắc chắn, về mặt kỹ thuật, có thể giải quyết thách thức này bằng vũ lực. Tuy nhiên, đây chính xác là một trong những tình huống mà chiếc búa của chúng ta rõ ràng là công cụ sai

Giải pháp brute force sẽ sử dụng các vòng lặp lồng nhau để tìm TẤT CẢ các mảng con (i. e. phần của một mảng) của một mảng đã cho, sau đó so sánh chúng để xem cái nào cộng lại thành tổng lớn nhất. Nếu một mảng rất lớn, độ phức tạp về thời gian của thao tác này có thể là thảm họa

Càng rõ ràng hơn về mức độ nghèo nàn của một công cụ khi tiếp cận giải pháp này khi chúng tôi xem xét rằng nhiều ứng dụng của thử thách này yêu cầu tìm tổng mảng con tối đa của toàn bộ ma trận của mảng hai chiều, làm tăng độ phức tạp thời gian logarit của giải pháp này

Thật may mắn cho chúng ta, Jay Kadane đã phát triển một thuật toán đáng yêu chỉ để giải bài toán đặc biệt này càng nhanh càng tốt. Nó chạy trong thời gian tuyến tính. Đó chỉ là thứ chúng ta muốn. Đó là một công cụ tìm kiếm giải pháp tinh tế và là một lời nhắc nhở tuyệt vời rằng đôi khi, sử dụng một chiếc búa tiện dụng có thể gây ra nhiều vấn đề hơn là giải quyết được

Hãy phác thảo khuôn khổ của chúng tôi

Để bắt đầu, chúng ta sẽ chuyển dãy số của mình vào một hàm mà tôi gọi là largeSubarraySum, sau đó xác định hai biến đặc biệt — currentSum và largeSum

Thuật toán của Kadane yêu cầu chúng ta lặp lại một lần thông qua mảng của chúng ta. Chúng ta đã đạt được điều này trong giàn giáo chức năng ban đầu của mình, nhưng chính xác thì chúng ta sẽ làm gì bên trong vòng lặp mà chúng ta đã chuẩn bị?

Logic của thuật toán yêu cầu chúng ta gán một giá trị mới cho biến currentSum mà chúng ta đã chuẩn bị. Đối với mỗi số trong mảng của chúng tôi, chúng tôi có thể gán lại currentSum thành giá trị 0 hoặc tổng mới của currentSum và số, tùy theo giá trị nào lớn hơn

Điều này đảm bảo rằng currentSum không bao giờ có thể là số âm

Có thêm một chút logic bên trong vòng lặp này. Chúng tôi chưa hoàn thành

Trước khi chuyển sang phần tử tiếp theo trong mảng, chúng ta cần so sánh currentSum với largeSum

Nếu currentSum lớn hơn largeSum, thì chúng ta cần thay thế largeSum cũ bằng tổng lớn nhất mới, i. e. hiện tạiSum

Vì vậy, điều này trông như thế nào trong Javascript?

Xem qua mã này, nó hoạt động đúng như chúng tôi đã lên kế hoạch

Lướt qua bên trái để viết, từng dòng một, chúng ta có thể thấy rằng chúng ta đang gán một giá trị mới cho biến currentSum của mình. Giá trị đó sẽ là bất cứ thứ gì được trả về bởi những gì chúng ta chuyển vào Javascript's Math. hàm tối đa (). Trong trường hợp của chúng tôi, chúng tôi yêu cầu Javascript trả lại bất kỳ giá trị nào lớn hơn. bằng 0 hoặc tổng của currentSum và số (phần tử mảng hiện tại)

Sau đó, chúng tôi gán một giá trị mới cho largeSum — bất kỳ giá trị nào trong số largeSum hoặc currentSum được xác định là số lớn hơn và được trả về bởi Math. tối đa()

Hai đánh giá này sẽ xảy ra cho mọi phần tử mới trong mảng, có nghĩa là largeSum sẽ là số được lưu từ bất kỳ đoạn nào của mảng con kết thúc mang lại tổng lớn nhất — mọi tổng của mảng con tiếp theo được lưu vào currentSum sẽ không thay thế cho largeSum vì chúng sẽ không thay thế . tối đa()

Bây giờ, nếu chúng tôi đang tìm kiếm một giải pháp hiệu quả, bạn có thể đặt câu hỏi về việc sử dụng Javascript's Math. hàm tối đa (). Xét cho cùng, khi có quá nhiều con số được chuyển vào môn Toán. max() để so sánh, nó có thể trở nên rắc rối. Tuy nhiên, chúng tôi không bao giờ cần phải so sánh nhiều hơn hai số cùng một lúc, làm cho công cụ này trở thành một công cụ tính toán hiệu quả và hiệu quả

Đó là tất cả tốt và tốt, nhưng chúng tôi cần đảm bảo rằng điều này thực sự, bạn biết đấy, hoạt động

Tôi có một số mảng số và tổng của mảng con lớn nhất tương ứng của chúng đã sẵn sàng hoạt động, vì vậy chúng ta có thể đưa hàm của mình ngay vào bảng điều khiển và xem liệu nó có tìm đúng tổng lớn nhất không

Tuyệt quá. 🌟 Chức năng của chúng tôi dường như đang tìm tổng mảng con chính xác cho nhiều mảng số với các đặc điểm khác nhau

Nếu bạn muốn biết thêm về mục đích thử nghiệm của từng mảng được sử dụng ở trên, bạn có thể đọc bộ thử nghiệm có trong repo GitHub của mã giải pháp cho thử thách này

Đối với tôi, cách tiếp cận này thú vị hơn nhiều so với việc tạo ra một đống lớn các mảng con và so sánh chúng. Tôi nghĩ thật dễ dàng để giả định rằng các giải pháp thuật toán hoặc các giải pháp vượt trội khác tự động phức tạp hơn hoặc khó làm việc hơn so với các giải pháp bạo lực, nhưng tôi nghĩ thuật toán của Kadane là một minh họa tuyệt vời về việc điều đó không phải lúc nào cũng đúng. Nó cũng ít có khả năng khiến chúng tôi gặp phải lỗi thời gian chạy do quá phức tạp về thời gian/không gian

Hy vọng rằng việc có thuật toán của Kadane trong bộ công cụ của bạn sẽ giúp bạn thành công hơn trong việc tìm tổng phân đoạn lớn nhất so với anh chàng này