เราจะพัฒนาโปรแกรม C++ เพื่อหาผลรวมสับอาร์เรย์สูงสุด (maximum subarray sum) ในเวลา O(n^2) โดยใช้วิธี naive
อัลกอริทึม
Begin รับองค์ประกอบอาร์เรย์เป็นอินพุท ทำลูปสำหรับความยาวของสับอาร์เรย์จาก 1 ถึง n ภายในลูปนี้ ทำลูปซ้อนอีกทีหนึ่งกับลูปก่อนหน้า คำนวณผลรวมของสับอาร์เรย์แรกของความยาวนั้น สำหรับผลรวมสับอาร์เรย์ที่เหลือ ให้บวกองค์ประกอบถัดไปเข้ากับผลรวมและลบองค์ประกอบแรกของสับอาร์เรย์นั้น เปรียบเทียบกับค่าสูงสุดทั่วไป (global max) และอัปเดตถ้าพบว่ามากกว่า พิมพ์สับอาร์เรย์สูงสุดและผลรวมของพวกเขาเป็นผลลัพธ์ End
ตัวอย่างโค้ด
#include<iostream> using namespace std; int main() { int n, i, j, m=-1, s, ini_m, fi_m; cout<<"\nEnter the number of data element in the array: "; cin>>n; int a[n]; for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>a[i]; } for(i = 1; i < n+1; i++) { s = 0; for(j = 0; j < n; j++) { if(j < i) s += a[j]; else s = s+a[j]-a[j-i]; if(m< s) { ini_m = j-i+1; fi_m = j; m = s; } } } cout<<"\nThe maximum sub array is: "; for(i = ini_m; i <= fi_m; i++) cout<<a[i]<<" "; cout<<"\nThe maximum sub-array sum is: "<<m; }
ผลลัพธ์
Enter the number of data element in the array: 10 Enter element 1: 1 Enter element 2: -2 Enter element 3: 3 Enter element 4: -4 Enter element 5: 5 Enter element 6: -6 Enter element 7: 7 Enter element 8: 8 Enter element 9: -9 Enter element 10: 10 The maximum sub array is: 7 8 -9 10 The maximum sub-array sum is: 16
