Our first algorithm for the maximum

Our first algorithm for the maximum subarray problem, which we call MaxsubSlow,
is shown in Algorithm 1.14. It computes the maximum of every possible
subarray summation, sj,k, of A separately

It isn’t hard to see that the MaxsubSlow algorithm is correct. This algorithm
calculates the partial sum, sj,k, of every possible subarray, by adding up the values
in the subarray A[j : k]. Moreover, for every such subarray sum, it compares that
sum to a running maximum and if the new value is greater than the old, it updates
that maximum to the new value. In the end, this will be maximum subarray sum.
Incidentally, both the calculating of subarray summations and the computing of
the maximum so far are examples of an accumulator pattern, where we incrementally
accumulate values into a single variable to compute a sum or maximum (or
minimum). This is a pattern that is used in a lot of algorithms, but in this case it is
not being used in the most efficient way possible.
Analyzing the running time of the MaxsubSlow algorithm is easy. In particular,
the outer loop, for index j, will iterate n times, its inner loop, for index k, will
iterate at most n times, and the inner-most loop, for index i, will iterate at most n
times. Thus, the running time of the MaxsubSlow algorithm is O(n3). Unfortunately,
in spite of its use of the accumulator design pattern, giving the MaxsubSlow
algorithm as a solution to the maximum subarray problem would be a bad idea during
a job interview. This is a slow algorithm for the maximum subarray problem.

ผลลัพธ์ (ไทย) 1:

อัลกอริทึมของเราแรกสำหรับปัญหา subarray สูงสุด ซึ่งเราเรียกว่า MaxsubSlowแสดงในสุรา 1.14 อัลกอริทึมนี้ มันคำนวณสูงสุดไปได้ทุกsubarray รวม เอสเจ k ของแยกต่างหากไม่หนักจะเห็นได้ว่า อัลกอริทึม MaxsubSlow ถูกต้อง อัลกอริทึมนี้คำนวณผลรวมบางส่วน เอสเจ k ของทุก subarray ได้ โดยการเพิ่มค่าใน subarray A [j: k] นอกจากนี้ สำหรับทุกเช่น subarray ผล มันเปรียบเทียบที่ผลการทำงานที่สูงสุด และถ้าค่ามีค่ามากกว่าเก่าสูงสุดที่ค่าใหม่ ในสุด นี้จะเป็นผลรวมสูงสุด subarrayบังเอิญ ทั้งการคำนวณ subarray ออกและการใช้งานของสูงสุดจนเป็นตัวอย่างของรูปแบบการสะสม ที่เราแบบเพิ่มหน่วยสะสมค่าลงในตัวแปรเดียวในการคำนวณผลรวมหรือสูงสุด (หรือค่าต่ำสุด) นี้คือรูปแบบที่ใช้ในอัลกอริทึมมาก แต่ในกรณีนี้ ก็ไม่ได้ใช้ในวิธีมีประสิทธิภาพได้การวิเคราะห์เวลาทำงานของอัลกอริทึม MaxsubSlow เป็นเรื่องง่าย โดยเฉพาะวงด้านนอก สำหรับดัชนี j จะวนซ้ำ n ครั้ง จะห่วงของภายใน สำหรับดัชนี kทำซ้ำในที่สุด n ครั้ง และวนรอบชั้นในสุด สำหรับดัชนีที่ฉัน จะทำซ้ำในที่สุด nครั้ง ดังนั้น เวลาทำงานของอัลกอริทึม MaxsubSlow เป็น O(n3) อับทั้ง ๆ ที่ มีการใช้รูปแบบการออกแบบชื้น ให้ MaxsubSlowอัลกอริทึมเป็นวิธีแก้ไขปัญหา subarray สูงสุดจะเป็นความคิดไม่ดีระหว่างการสัมภาษณ์งาน อัลกอริทึมช้าปัญหา subarray สูงสุดได้

ผลลัพธ์ (ไทย) 2:

อัลกอริทึมแรกของเราสำหรับปัญหา subarray สูงสุดที่เราเรียก MaxsubSlow,
ปรากฏอยู่ในขั้นตอนวิธี 1.14 มันคำนวณสูงสุดของทุกคนที่เป็นไปได้บวก subarray, SJ, k, ของที่แยกจากกันมันไม่ยากที่จะเห็นว่าขั้นตอนวิธีการที่ถูกต้องMaxsubSlow อัลกอริทึมนี้คำนวณผลรวมบางส่วน SJ, k ของ subarray เป็นไปได้ทุกคนโดยการเพิ่มขึ้นค่าในsubarray [เจ: k] นอกจากนี้สำหรับทุกคนเช่นผลรวม subarray ก็เปรียบเทียบว่าผลรวมสูงสุดทำงานและถ้าค่าใหม่มากกว่าเก่าก็ปรับปรุงสูงสุดที่จะค่าใหม่ ในท้ายที่สุดนี้จะเป็นสูงสุดผลรวม subarray. อนึ่งทั้งการคำนวณของ summations subarray และคอมพิวเตอร์ของสูงสุดเพื่อให้ห่างไกลเป็นตัวอย่างของรูปแบบการสะสมที่เราเพิ่มขึ้นสะสมค่าลงตัวแปรเดียวที่จะคำนวณผลรวมหรือสูงสุด ( หรือขั้นต่ำ) นี่คือรูปแบบที่ถูกนำมาใช้ในจำนวนมากของขั้นตอนวิธีการ แต่ในกรณีนี้มันจะไม่ได้ถูกนำมาใช้ในวิธีที่มีประสิทธิภาพมากที่สุด. การวิเคราะห์เวลาทำงานของอัลกอริทึม MaxsubSlow เป็นเรื่องง่าย โดยเฉพาะอย่างยิ่งห่วงด้านนอกสำหรับเจดัชนีจะย้ำ n ครั้งภายในห่วงสำหรับดัชนี k จะย้ำn ที่มากที่สุดครั้งและภายในห่วงมากที่สุดสำหรับดัชนีฉันจะย้ำที่มากที่สุด n ครั้ง ดังนั้นเวลาทำงานของอัลกอริทึม MaxsubSlow O (N3) แต่น่าเสียดายทั้งๆที่มีการใช้งานของรูปแบบการออกแบบสะสมให้ MaxsubSlow ขั้นตอนวิธีการเป็นวิธีแก้ปัญหาปัญหา subarray สูงสุดจะเป็นความคิดที่ดีในระหว่างการสัมภาษณ์งาน นี่คือขั้นตอนวิธีการช้าปัญหาสูงสุด subarray