s53Ffs - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;

long long numOfSubsequences(string s) {
        int n = s.length();
        if(n == 1) return 0;

        int l = 0, c = 0, t= 0, lc = 0, ct = 0, lct = 0;
        vector<int> prefixL(n);
        vector<int> suffixT(n);
        for (int i = 0; i < n; i++){
        	if(s[i] == 'L') {
        		l++;
        	}
        	if(s[i] == 'C'){
        		lc += l;
        		c++;
        	}

        	if(s[i] == 'T'){
        		lct += lc;
        		ct += c;
        	}

        	prefixL[i] = l;
        }


        for (int j = n-1; j >= 0; j--){
        	if(s[j] == 'T') t++;
        	suffixT[j] = t;
        }


        // Case 1 -Inserting 'L' at the front
        // ans = old count of "LCT" + total "CT" in the string.
        int ans1 = lct + ct;


        // Case 2 - Insering 'T' at the end
        // ans = old count of "LCT" + total "LC" in the string.
        int ans2 = lct + lc;


        int max1 = max(ans1, ans2);

        // Case 3 - Inserting 'C' at every position to maximize the count of "LCT"
        // Hence there is no need to insert 'C' at first and the end.
        int maxc = 0;
        for (int k = 0; k < n-1; k++){
        	int temp = prefixL[k] * suffixT[k+1];
        	maxc = max(maxc, temp);
        }

        int ans3 = lct + maxc;

        return max(ans3, max1);
    }

int main() {
	// your code goes here

	string s = "LCLPTTGC";
	cout << numOfSubsequences(s);

	return 0;
}