คำอธิบายปัญหา
กำหนดสตริงที่ประกอบด้วย 0 และ 1 งานคือการหาความยาวสูงสุดของเซกเมนต์ของสตริงที่จำนวน 1 ในแต่ละเซกเมนต์มากกว่า 0
ตัวอย่าง
ถ้าสตริงนำเข้าคือ "10111000001011" คำตอบจะเป็น 12 ดังนี้:
- เซกเมนต์แรกมีความยาว 7: 10111000001011
- เซกเมนต์ที่สองมีความยาว 5: 10111000001011
- ความยาวรวมคือความยาวของ (เซกเมนต์ 1 + เซกเมนต์ 2) = (7 + 5) = 12
อัลกอริทึม
- ถ้า start == n ให้คืนค่า 0
- รันลูปจาก start ถึง n คำนวณสำหรับแต่ละซับอาร์เรย์จนถึง n
- ถ้าตัวอักษรคือ 1 ให้เพิ่มจำนวน 1 ไป 1 มิฉะนั้นเพิ่มจำนวน 0 ไป 1
- ถ้าจำนวน 1 มากกว่าจำนวน 0 ให้เรียกฟังก์ชันซ้ำสำหรับดัชนี (k+1) คือดัชนีถัดไป และบวกความยาวที่เหลือ คือ k-start+1
- มิฉะนั้น ให้เรียกฟังก์ชันซ้ำสำหรับดัชนีถัดไป k+1 เท่านั้น
- คืนค่า dp[start]
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; int getSegmentWithMaxLength(int start, string str, int n, int dp[]) { if (start == n) { return 0; } if (dp[start] != -1) { return dp[start]; } dp[start] = 0; int one = 0; int zero = 0; int k; for (k = start; k < n; ++k) { if (str[k] == '1') { ++one; } else { ++zero; } if (one > zero) { dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp) + k - start + 1); } else { dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp)); } } return dp[start]; } int main() { string str = "10111000001011"; int n = str.size(); int dp[n + 1]; memset(dp, -1, sizeof(dp)); cout << "Maximum length of segment = " << getSegmentWithMaxLength(0, str, n, dp) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Maximum length of segment = 12
