[907] Sum of Subarray Minimums (TBD)

算一個array裡面的 "連續subarray" 的最小值相加

就是 (1,2,3,4) 的話, subarray 是1,2,3,4 跟 (1,2) (2,3) (3,4) (1,2,3) (2,3,4) (1,2,3,4) 

(1,3)跟(2,4)這種因為不連續所以不在這裡定義的subarray. 

一開始想說要開一個int subarray 把它們都存起來

所以想算subarray總共有幾組，也就是 n! 長度的階乘，

但後來發現其實沿路算下去就好了，不需要先把subarray都先存起來

再來就發現超時了 XD

但看起來是對的(吧) 那只好先這樣，晚點我再看看其他人都怎麼寫 XD

int sumSubarrayMins(int* arr, int arrSize){

// printf("arrSize %d\n", arrSize);

long ret=0;

for (int l=1;l<=arrSize;l++)

{

for (int i=0;i<=(arrSize-l);i++)

{

int min=INT_MAX;

for (int j=0;j<l;j++)

{

if (arr[i+j] < min)

min=arr[i+j];

}

ret += min;

}

}

int retInt= ret%(1000000000+7);

return retInt;

}

啊DP好難