Simple  1D dp C++
\n\nVariables:\n\nn represents the size of the input array nums.\nstart keeps track of the starting index of the segment.\nans stores the maximum number of priz
\n\nVariables:\n\nn represents the size of the input array nums.\nstart keeps track of the starting index of the segment.\nans stores the maximum number of prizes won.\ndp is an auxiliary array that keeps track of the maximum number of prizes that can be won up to the current index.\n\n\nIterate through the elements of prizePositions using the variable i:\n\nInside the loop, we find the maximum value of start such that prizePositions[i] - prizePositions[start] <= k. This means we find the leftmost element within k distance from prizePositions[i].\nUpdate ans by comparing the current maximum with the length of the current segment (i - start + 1) plus the maximum number of prizes won from the previous segment (start > 0 ? dp[start - 1] : 0).\nUpdate dp[i] by comparing the maximum number of prizes won up to the previous index (i > 0 ? dp[i - 1] : 0) with the length of the current segment (i - start + 1).\nReturn the maximum number of prizes won, which is stored in ans.\n\nThe main idea behind this approach is to find the maximum number of prizes that can be won by selecting two segments of length k or less. By keeping track of the starting index start and updating the dp array, the algorithm efficiently finds the optimal solution in a single pass through the prizePositions array.\n\nThe time complexity of this code is O(n), where n is the size of the input array prizePositions. The space complexity is O(n) as well, due to the dp array.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    \n        int maximizeWin(vector<int>& prizePositions, int k) \n        {\n            int n=prizePositions.size();\n            int start =0; int ans=0;\n            vector<int> dp(n);\n            for(int i=0;i<n;i++)\n            {\n                //find leftmost element with k segement\n                while(prizePositions[i]-prizePositions[start]>k) start++;\n                //calculate this segment length\n                int segmentLength = i-start+1;\n                //maintain ans, sum of two segemtn, curr+ use dp for previous one \n                ans = max(ans,segmentLength+(start>0?dp[start-1]:0));\n                //update dp[i] which store maxlenght upto this index\n                dp[i] = max((i>0 ? dp[i-1]:0),segmentLength);\n            }\n            return ans;\n        }\n    \n//     int maximizeWin(vector<int>& prizePositions, int k) {\n//         //FIrst to intersect na hi kr to theek , But kabhi forceful krana pdega\n//         //maintain two max\n        \n//         int max1=INT_MIN,max2 =INT_MIN;\n//         for(int i=0;i<prizePositions.size();i++)\n//         {\n//             int val =prizePositions[i];\n//             int target = val+k-1; //isse bade wala pinter nikalo\n//             int len = upper_bound(prizePositions.begin()+i,prizePositions.end(),target) - (prizePositions.begin()+i) ;\n//             if(len>=max1)\n//             {\n//                 max2 =max1;\n//                 max1 = len;\n//             }\n//             //update i to the pointer iterator \n//             i=i+len; //But yhn cases miss honge overlap wale\n//         }\n//         return max1+max2;\n//     }\n};\n```
['C++']