คำชี้แจงปัญหา
กำหนดสตริงที่ประกอบด้วยหนึ่งและศูนย์ ภารกิจคือการค้นหาความยาวสูงสุดของเซ็กเมนต์ของสตริงเพื่อให้จำนวน 1 ในแต่ละเซ็กเมนต์มีค่ามากกว่า 0
ตัวอย่าง
หากสตริงอินพุตคือ “10111000001011” คำตอบจะเป็น 12 ดังนี้ −
- ส่วนแรกมีความยาว 7 1011100000001011
- ส่วนที่สองมีความยาว 5 10111000001011
- ความยาวทั้งหมดคือความยาวของ (ส่วนที่ 1 + กลุ่มที่ 2) =(7 + 5) =12
อัลกอริทึม
- ถ้า start ==n ให้คืนค่า 0
- เรียกใช้การวนซ้ำตั้งแต่ต้นจนถึง n คำนวณสำหรับแต่ละอาร์เรย์ย่อยจนถึง n
- หากอักขระเป็น 1 ให้เพิ่มจำนวน 1 ตัว มิฉะนั้นจะเพิ่มจำนวนเป็น 0
- หากจำนวน 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
