SkylineWebZ

Problem Statement: Word Break Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: Example Example 1: Input: s = “leetcode”, wordDict = [“leet”, “code”]Output: trueExplanation: Return true because “leetcode” can be segmented as “leet code”. Example 2: Input: s = “applepenapple”, wordDict = [“apple”, “pen”]Output: trueExplanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Example 3: Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]Output: falseExplanation: Return false because “catsandog” cannot be segmented into words from the dictionary. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>bool wordBreak(char* s, char** wordDict, int wordDictSize) { int n = strlen(s); bool dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < wordDictSize; j++) { int len = strlen(wordDict[j]); if (i >= len && dp[i – len] && strncmp(s + i – len, wordDict[j], len) == 0) { dp[i] = true; break; } } } return dp[n];}int main() { char* wordDict[] = {“leet”, “code”}; int wordDictSize = sizeof(wordDict) / sizeof(wordDict[0]); char s[] = “leetcode”; printf(“%d\n”, wordBreak(s, wordDict, wordDictSize)); // Output: 1 (true) return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>using namespace std;bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } return dp[n];}int main() { vector<string> wordDict = {“leet”, “code”}; string s = “leetcode”; cout << wordBreak(s, wordDict) << endl; // Output: 1 (true) return 0;} Java import java.util.*;public class WordBreak { public static boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } public static void main(String[] args) { List<String> wordDict = Arrays.asList(“leet”, “code”); String s = “leetcode”; System.out.println(wordBreak(s, wordDict)); // Output: true }} Python def wordBreak(s: str, wordDict: list) -> bool: wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[n]# Examples = “leetcode”wordDict = [“leet”, “code”]print(wordBreak(s, wordDict)) # Output: True C# using System;using System.Collections.Generic;public class WordBreak { public static bool WordBreak(string s, IList<string> wordDict) { HashSet<string> wordSet = new HashSet<string>(wordDict); int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.Contains(s.Substring(j, i – j))) { dp[i] = true; break; } } } return dp[n]; } public static void Main() { List<string> wordDict = new List<string> { “leet”, “code” }; string s = “leetcode”; Console.WriteLine(WordBreak(s, wordDict)); // Output: True }} JavaScript function wordBreak(s, wordDict) { const wordSet = new Set(wordDict); const n = s.length; const dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { if (dp[j] && wordSet.has(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n];}console.log(wordBreak(“leetcode”, [“leet”, “code”])); // Output: true Summary

Problem Statement: Palindrome Partitioning II Given a string s, you need to partition it such that every substring of the partition is a palindrome. Return the minimum number of cuts required to partition s such that every substring is a palindrome. Example Example 1: Input: s = “aab” Output: 1Explanation: The palindrome partitioning [“aa”, “b”] could be made with 1 cut. Example 2: Input: s = “a” Output: 0Explanation: The string is already a palindrome, so no cuts are needed. Example 3: Input: s = “abac” Output: 1Explanation: The palindrome partitioning [“aba”, “c”] could be made with 1 cut. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>#define MAX 1000int minCut(char* s) { int n = strlen(s); bool palindrome[n][n]; int dp[n+1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; memset(palindrome, 0, sizeof(palindrome)); for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = (dp[i] < dp[j] + 1) ? dp[i] : dp[j] + 1; } } } return dp[n – 1];}int main() { char s[] = “aab”; printf(“%d\n”, minCut(s)); return 0;} C++ #include <iostream>#include <vector>#include <cstring>using namespace std;int minCut(string s) { int n = s.length(); vector<vector<bool>> palindrome(n, vector<bool>(n, false)); vector<int> dp(n + 1, n); dp[0] = -1; // no cut needed for empty string for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1); } } } return dp[n – 1];}int main() { string s = “aab”; cout << minCut(s) << endl; return 0;} Java public class PalindromePartitioning { public static int minCut(String s) { int n = s.length(); boolean[][] palindrome = new boolean[n][n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s.charAt(i) == s.charAt(j)) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void main(String[] args) { String s = “aab”; System.out.println(minCut(s)); }} Python def minCut(s: str) -> int: n = len(s) palindrome = [[False] * n for _ in range(n)] dp = [i for i in range(-1, n)] for i in range(n – 1, -1, -1): for j in range(i, n): palindrome[i][j] = (s[i] == s[j]) and (j – i <= 2 or palindrome[i + 1][j – 1]) for i in range(n): if palindrome[0][i]: dp[i] = 0 else: for j in range(i): if palindrome[j + 1][i]: dp[i] = min(dp[i], dp[j] + 1) return dp[n – 1]# Examples = “aab”print(minCut(s)) # Output: 1 C# using System;public class PalindromePartitioning { public static int MinCut(string s) { int n = s.Length; bool[,] palindrome = new bool[n, n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i, j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1, j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0, i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1, i]) dp[i] = Math.Min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void Main() { string s = “aab”; Console.WriteLine(MinCut(s)); // Output: 1 }} JavaScript function minCut(s) { const n = s.length; const palindrome = Array.from(Array(n), () => Array(n).fill(false)); const dp = Array.from({ length: n + 1 }, (_, i) => i – 1); for (let i = n – 1; i >= 0; i–) { for (let j = i; j < n; j++) { palindrome[i][j] = (s[i] === s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (let i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (let j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1];}console.log(minCut(“aab”)); // Output: 1 Summary

Problem Statement: Palindrome Partitioning Given a string s, partition the string such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Definition: Example: Example 1: Input: plaintextCopy code”aab” Output: plaintextCopy code[[“a”, “a”, “b”], [“aa”, “b”]] Explanation: The string “aab” can be split in two ways where each substring is a palindrome: Example 2: Input: plaintextCopy code”efe” Output: plaintextCopy code[[“e”, “f”, “e”], [“efe”]] Explanation: The string “efe” can be split into: Approach: We can solve this problem using backtracking and dynamic programming. Backtracking Approach: Algorithm: Code Implementation: 1. C++: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: bool isPalindrome(const string& s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) { if (start == s.length()) { result.push_back(current); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.push_back(s.substr(start, end – start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); // backtrack } } } vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> current; backtrack(s, 0, current, result); return result; }};int main() { Solution sol; string s = “aab”; vector<vector<string>> result = sol.partition(s); for (const auto& partition : result) { for (const auto& str : partition) { cout << str << ” “; } cout << endl; } return 0;} 2. Java: import java.util.ArrayList;import java.util.List;public class Solution { public boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start) != s.charAt(end)) return false; start++; end–; } return true; } public void backtrack(String s, int start, List<String> current, List<List<String>> result) { if (start == s.length()) { result.add(new ArrayList<>(current)); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.add(s.substring(start, end + 1)); backtrack(s, end + 1, current, result); current.remove(current.size() – 1); // backtrack } } } public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); List<String> current = new ArrayList<>(); backtrack(s, 0, current, result); return result; } public static void main(String[] args) { Solution sol = new Solution(); String s = “aab”; List<List<String>> result = sol.partition(s); for (List<String> partition : result) { for (String str : partition) { System.out.print(str + ” “); } System.out.println(); } }} 3. Python: class Solution: def isPalindrome(self, s, start, end): while start < end: if s[start] != s[end]: return False start += 1 end -= 1 return True def backtrack(self, s, start, current, result): if start == len(s): result.append(list(current)) return for end in range(start, len(s)): if self.isPalindrome(s, start, end): current.append(s[start:end+1]) self.backtrack(s, end+1, current, result) current.pop() # backtrack def partition(self, s): result = [] self.backtrack(s, 0, [], result) return result# Example usagesol = Solution()s = “aab”result = sol.partition(s)for partition in result: print(partition) 4. C#: using System;using System.Collections.Generic;public class Solution { public bool IsPalindrome(string s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } public void Backtrack(string s, int start, List<string> current, List<List<string>> result) { if (start == s.Length) { result.Add(new List<string>(current)); return; } for (int end = start; end < s.Length; ++end) { if (IsPalindrome(s, start, end)) { current.Add(s.Substring(start, end – start + 1)); Backtrack(s, end + 1, current, result); current.RemoveAt(current.Count – 1); // backtrack } } } public List<List<string>> Partition(string s) { List<List<string>> result = new List<List<string>>(); List<string> current = new List<string>(); Backtrack(s, 0, current, result); return result; } public static void Main() { Solution sol = new Solution(); string s = “aab”; List<List<string>> result = sol.Partition(s); foreach (var partition in result) { Console.WriteLine(string.Join(” “, partition)); } }} 5. JavaScript: class Solution { isPalindrome(s, start, end) { while (start < end) { if (s[start] !== s[end]) return false; start++; end–; } return true; } backtrack(s, start, current, result) { if (start === s.length) { result.push([…current]); return; } for (let end = start; end < s.length; ++end) { if (this.isPalindrome(s, start, end)) { current.push(s.substring(start, end + 1)); this.backtrack(s, end + 1, current, result); current.pop(); // backtrack } } } partition(s) { let result = []; this.backtrack(s, 0, [], result); return result; }}// Example usage:let sol = new Solution();let s = “aab”;let result = sol.partition(s);result.forEach(partition => { console.log(partition.join(” “));}); Time and Space Complexity:

Problem Statement: Binary Tree Maximum Path Sum Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree, and you are allowed to move from a node to its left or right child but not upwards to its parent. Path Definition: A path is a sequence of nodes in the tree where each pair of adjacent nodes in the sequence has an edge connecting them. The sum of the path is the sum of the node values along the path. Example: Example 1: Input: -10 / \ 9 20 / \ 15 7 Output: 42 Explanation: The path with the maximum sum is 15 -> 20 -> 7, which sums to 15 + 20 + 7 = 42. Example 2: Input: 1 / \ 2 3 Output: 6 Explanation: The path with the maximum sum is 2 -> 1 -> 3, which sums to 2 + 1 + 3 = 6. Approach: Algorithm: Code Implementation: 1. C: #include <stdio.h>#include <limits.h>struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;};int maxPathSumHelper(struct TreeNode* root, int* globalMax) { if (root == NULL) { return 0; } int left = maxPathSumHelper(root->left, globalMax); int right = maxPathSumHelper(root->right, globalMax); int maxSingle = (left > right) ? left : right; maxSingle = (maxSingle > 0) ? maxSingle + root->val : root->val; int maxTop = left + right + root->val; *globalMax = (*globalMax > maxTop) ? *globalMax : maxTop; return maxSingle;}int maxPathSum(struct TreeNode* root) { int globalMax = INT_MIN; maxPathSumHelper(root, &globalMax); return globalMax;}int main() { struct TreeNode n1 = { -10, NULL, NULL }; struct TreeNode n2 = { 9, NULL, NULL }; struct TreeNode n3 = { 20, NULL, NULL }; struct TreeNode n4 = { 15, NULL, NULL }; struct TreeNode n5 = { 7, NULL, NULL }; n1.left = &n2; n1.right = &n3; n3.left = &n4; n3.right = &n5; printf(“Maximum Path Sum: %d\n”, maxPathSum(&n1)); return 0;} 2. C++: #include <iostream>#include <climits>using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public: int maxPathSumHelper(TreeNode* root, int& globalMax) { if (!root) return 0; int left = max(0, maxPathSumHelper(root->left, globalMax)); int right = max(0, maxPathSumHelper(root->right, globalMax)); int localMax = left + right + root->val; globalMax = max(globalMax, localMax); return max(left, right) + root->val; } int maxPathSum(TreeNode* root) { int globalMax = INT_MIN; maxPathSumHelper(root, globalMax); return globalMax; }};int main() { TreeNode n1(-10), n2(9), n3(20), n4(15), n5(7); n1.left = &n2; n1.right = &n3; n3.left = &n4; n3.right = &n5; Solution sol; cout << “Maximum Path Sum: ” << sol.maxPathSum(&n1) << endl; return 0;} 3. Java: class Solution { int maxPathSumHelper(TreeNode root, int[] globalMax) { if (root == null) return 0; int left = Math.max(0, maxPathSumHelper(root.left, globalMax)); int right = Math.max(0, maxPathSumHelper(root.right, globalMax)); int localMax = left + right + root.val; globalMax[0] = Math.max(globalMax[0], localMax); return Math.max(left, right) + root.val; } public int maxPathSum(TreeNode root) { int[] globalMax = { Integer.MIN_VALUE }; maxPathSumHelper(root, globalMax); return globalMax[0]; }}class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; }}public class Main { public static void main(String[] args) { TreeNode n1 = new TreeNode(-10); TreeNode n2 = new TreeNode(9); TreeNode n3 = new TreeNode(20); TreeNode n4 = new TreeNode(15); TreeNode n5 = new TreeNode(7); n1.left = n2; n1.right = n3; n3.left = n4; n3.right = n5; Solution sol = new Solution(); System.out.println(“Maximum Path Sum: ” + sol.maxPathSum(n1)); }} 4. Python: class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def maxPathSumHelper(self, root, globalMax): if not root: return 0 left = max(0, self.maxPathSumHelper(root.left, globalMax)) right = max(0, self.maxPathSumHelper(root.right, globalMax)) localMax = left + right + root.val globalMax[0] = max(globalMax[0], localMax) return max(left, right) + root.val def maxPathSum(self, root: TreeNode) -> int: globalMax = [float(‘-inf’)] self.maxPathSumHelper(root, globalMax) return globalMax[0]# Example usageif __name__ == “__main__”: n1 = TreeNode(-10) n2 = TreeNode(9) n3 = TreeNode(20) n4 = TreeNode(15) n5 = TreeNode(7) n1.left = n2 n1.right = n3 n3.left = n4 n3.right = n5 sol = Solution() print(“Maximum Path Sum:”, sol.maxPathSum(n1)) 5. C#: public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; }}public class Solution { public int MaxPathSumHelper(TreeNode root, ref int globalMax) { if (root == null) return 0; int left = Math.Max(0, MaxPathSumHelper(root.left, ref globalMax)); int right = Math.Max(0, MaxPathSumHelper(root.right, ref globalMax)); int localMax = left + right + root.val; globalMax = Math.Max(globalMax, localMax); return Math.Max(left, right) + root.val; } public int MaxPathSum(TreeNode root) { int globalMax = int.MinValue; MaxPathSumHelper(root, ref globalMax); return globalMax; }}// Example usage:class Program { static void Main(string[] args) { TreeNode n1 = new TreeNode(-10); TreeNode n2 = new TreeNode(9); TreeNode n3 = new TreeNode(20); TreeNode n4 = new TreeNode(15); TreeNode n5 = new TreeNode(7); n1.left = n2; n1.right = n3; n3.left = n4; n3.right = n5; Solution sol = new Solution(); Console.WriteLine(“Maximum Path Sum: ” + sol.MaxPathSum(n1)); }} 6. JavaScript: class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}class Solution { maxPathSumHelper(root, globalMax) { if (!root) return 0; let left = Math.max(0, this.maxPathSumHelper(root.left, globalMax)); let right = Math.max(0, this.maxPathSumHelper(root.right, globalMax)); let localMax = left + right + root.val; globalMax[0] = Math.max(globalMax[0], localMax); return Math.max(left, right) + root.val; } maxPathSum(root) { let globalMax = [Number.NEGATIVE_INFINITY]; this.maxPathSumHelper(root, globalMax); return globalMax[0]; }}// Example usagelet n1 = new TreeNode(-10);let n2 = new TreeNode(9);let n3 = new TreeNode(20);let n4 = new TreeNode(15);let n5 = new TreeNode(7);n1.left = n2;n1.right = n3;n3.left = n4;n3.right = n5;let sol = new Solution();console.log(“Maximum Path Sum:”, sol.maxPathSum(n1)); Summary:

Problem Statement: Best Time to Buy and Sell Stock III You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. You can complete at most two transactions. In other words, you can make at most two buy-sell pairs. Each transaction consists of buying one stock and then selling it. You cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Return the maximum profit you can achieve. Example: Approach To solve this problem, we can use Dynamic Programming (DP) to track the maximum profit we can make with at most two transactions. The key idea is to break the problem into two subproblems: Dynamic Programming Approach: Steps: Code Implementation C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { if (pricesSize == 0) return 0; int first[pricesSize], second[pricesSize]; int minPrice = prices[0]; first[0] = 0; // no profit on the first day // Calculate maximum profit with at most one transaction up to day i for (int i = 1; i < pricesSize; i++) { first[i] = (prices[i] – minPrice > first[i – 1]) ? prices[i] – minPrice : first[i – 1]; minPrice = (prices[i] < minPrice) ? prices[i] : minPrice; } int maxPrice = prices[pricesSize – 1]; second[pricesSize – 1] = 0; // no profit on the last day // Calculate maximum profit with at most one transaction from day i to end for (int i = pricesSize – 2; i >= 0; i–) { second[i] = (maxPrice – prices[i] > second[i + 1]) ? maxPrice – prices[i] : second[i + 1]; maxPrice = (prices[i] > maxPrice) ? prices[i] : maxPrice; } int maxProfit = 0; for (int i = 0; i < pricesSize; i++) { maxProfit = (first[i] + second[i] > maxProfit) ? first[i] + second[i] : maxProfit; } return maxProfit;}int main() { int prices[] = {3,2,6,5,0,3}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 7 return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; vector<int> first(n, 0), second(n, 0); int minPrice = prices[0]; // Calculate maximum profit for the first transaction up to each day for (int i = 1; i < n; i++) { first[i] = max(first[i – 1], prices[i] – minPrice); minPrice = min(minPrice, prices[i]); } int maxPrice = prices[n – 1]; // Calculate maximum profit for the second transaction from each day for (int i = n – 2; i >= 0; i–) { second[i] = max(second[i + 1], maxPrice – prices[i]); maxPrice = max(maxPrice, prices[i]); } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = max(maxProfit, first[i] + second[i]); } return maxProfit;}int main() { vector<int> prices = {3,2,6,5,0,3}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 7 return 0;} Java: public class BestTimeToBuyAndSellStockIII { public static int maxProfit(int[] prices) { int n = prices.length; if (n == 0) return 0; int[] first = new int[n]; int[] second = new int[n]; // First transaction: calculate max profit up to each day int minPrice = prices[0]; for (int i = 1; i < n; i++) { first[i] = Math.max(first[i – 1], prices[i] – minPrice); minPrice = Math.min(minPrice, prices[i]); } // Second transaction: calculate max profit from each day to the end int maxPrice = prices[n – 1]; for (int i = n – 2; i >= 0; i–) { second[i] = Math.max(second[i + 1], maxPrice – prices[i]); maxPrice = Math.max(maxPrice, prices[i]); } // Max profit by combining both transactions int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, first[i] + second[i]); } return maxProfit; } public static void main(String[] args) { int[] prices = {3, 2, 6, 5, 0, 3}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 7 }} Python: def maxProfit(prices): n = len(prices) if n == 0: return 0 first = [0] * n second = [0] * n # First transaction: calculate max profit up to each day min_price = prices[0] for i in range(1, n): first[i] = max(first[i – 1], prices[i] – min_price) min_price = min(min_price, prices[i]) # Second transaction: calculate max profit from each day to the end max_price = prices[-1] for i in range(n – 2, -1, -1): second[i] = max(second[i + 1], max_price – prices[i]) max_price = max(max_price, prices[i]) # Max profit by combining both transactions max_profit = 0 for i in range(n): max_profit = max(max_profit, first[i] + second[i]) return max_profit# Example usageprices = [3, 2, 6, 5, 0, 3]print(“Max profit:”, maxProfit(prices)) # Output: 7 C#: using System;public class BestTimeToBuyAndSellStockIII { public static int MaxProfit(int[] prices) { int n = prices.Length; if (n == 0) return 0; int[] first = new int[n]; int[] second = new int[n]; // First transaction: calculate max profit up to each day int minPrice = prices[0]; for (int i = 1; i < n; i++) { first[i] = Math.Max(first[i – 1], prices[i] – minPrice); minPrice = Math.Min(minPrice, prices[i]); } // Second transaction: calculate max profit from each day to the end int maxPrice = prices[n – 1]; for (int i = n – 2; i >= 0; i–) { second[i] = Math.Max(second[i + 1], maxPrice – prices[i]); maxPrice = Math.Max(maxPrice, prices[i]); } // Max profit by combining both transactions int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.Max(maxProfit, first[i] + second[i]); } return maxProfit; } static void Main() { int[] prices = {3, 2, 6, 5, 0, 3}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 7 }} JavaScript: function maxProfit(prices) { const n = prices.length; if (n === 0) return 0; let first = Array(n).fill(0); let second = Array(n).fill(0); // First transaction: calculate max profit up to each day let minPrice = prices[0]; for (let i = 1; i < n; i++) { first[i] = Math.max(first[i – 1], prices[i] – minPrice); minPrice = Math.min(minPrice, prices[i]); } // Second transaction: calculate max profit from each